BubbleIntervalGraph
For a set of closed intervals on real line, one the can construct an interval graph. Represent each interval with a different graph vertex and connect two vertices if and only if two corresponding intervals have common points.
Does a the given tree represent an interval graph for some set of intervals?
InputThe first line contains positive integer n (1≤n≤1000000) — the number of nodes in a tree. The nodes are numbered by IDs: 0,1,2,…,n-1. The node 0 is the root node of the tree.
The next n lines describe children for all nodes.
Line i (each of n lines) lists all children of the node with ID i.
The first integer in the line is c [i], the number of child nodes of node i. The next c[i] integers in the same line are IDs of those child nodes.
The next n lines describe children for all nodes.
Line i (each of n lines) lists all children of the node with ID i.
The first integer in the line is c [i], the number of child nodes of node i. The next c[i] integers in the same line are IDs of those child nodes.
OutputThe output consists of one line:
- “yes” (without quotes) if the given tree represents an interval graph
- “no” if it doesn’t
- “yes” (without quotes) if the given tree represents an interval graph
- “no” if it doesn’t
Input:
3
1 2
0
1 1
Output:
yes
Input:
7
3 1 2 3
1 4
1 5
1 6
0
0
0
Output:
no
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.