7-Laboratoriya jumısı. Tema : Shuqırlıq boyınsha izlew algoritmı (dfs)

bool isupper(int v1, int v2) {
return tin[v1] <= tin[v2] && tout[v1] >= tout[v2];
}
int isfather(int v1, int v2) {
if (isupper(v1, v2))
return 1;
if (isupper(v2, v1))
return -1;
return 0;
}
Masalalar:


1-topshiriq
In this task you need to check whether the given undirected graph is connected. That it is possible to go from any vertex to any other along the edges of this graph.
Input
 The first line of the input are given numbers N and M are separated by
spaces – the number of vertices in the graph, respectively (1 ≤ N ≤ 10⁵, 
0 ≤ M ≤ 10⁵). The following M lines contain two numbers u_i and v_i by a
space (1 ≤ u_i, v_i ≤ N); each such line means that the graph there is an edge between vertices u_i and v_i.
Output
Bring out the "YES", if the graph is connected, and "NO" otherwise.
Samples

№	Input	Output
1	3 2 1 2 3 2	YES
2	3 1 1 3	NO

2-topshiriq
Tree is a connected and without cyclic graph. Undirected graph without loops and multiple edges is given with the adjacency matrix. Determine whether the graph is a tree.
Input
The first line contains the number of vertices n (1 ≤ n ≤ 400) in the graph. In the next lines the adjacency matrix of size n×n is given, where 1 denotes the presence of an edge, and 0 its absence. The matrix is symmetric with respect to the main diagonal.
Output
Print the message YES, if the graph is a tree, and NO otherwise.
Samples

№	Input	Output
1	3 0 1 0 1 0 1 0 1 0	YES
2	4 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0	NO

3-topshiriq
From a rectangular sheet of paper tartan (N rows, M columns) have removed some of the cells. How many pieces fall apart the rest of the sheet? Two cells do not break if they have a common side.
Input
 In the first row are the number of N and M, the following N lines - on M symbols. If the cell had not been cut, this corresponds to the # sign, if cut - a point. 1 ≤ N, M ≤ 1000. There is at least one # in input.
Output
 Print a single number – the answer to the problem.
Samples

№	Input	Output
1	4 8 #.##.#.# ......## #.###.## ##.##.##	6

4-topshiriq
We consider a geographical map with N countries numbered from 1 to N (0 < N < 99). For every country we know the numbers of other countries which are connected with its border. From every country we can reach to any other one, eventually crossing some borders. Write a program which determines whether it is possible to color the map only in two colors — red and blue in such a way that if two countries are connected their colors are different. The color of the first country is red. Your program must output one possible coloring for the other countries, or show, that such coloring is impossible.

Input

On the first line is written the number N. On the following N lines, the i-th line contains the countries to which the i-th country is connected. Every integer on this line is bigger than i, except the last one which is 0 and marks that no more countries are listed for country i. If a line contains 0, that means that the i-th country is not connected to any other country, which number is larger than i.

Output

The output contains exactly one line. If the coloring is possible, this line must contain a list of zeros and ones, without any separators between them. The i-th digit in this sequence is the color of the i-th country. 0 corresponds to red color, and one — to blue color. If a coloring is not possible, output the integer −1.

Sample

input	output
3 2 0 3 0 0	010

5-topshiriq
It is very hard for one person to learn all galactic history. But, on the other hand, every diplomat who wants to hold a more important post in a galactic empire must know the subject well. For example, letting a spoon fall among high-rankers of the star system Arcturus means offending them awfully. (Didn’t you hear that the last conflict between systems Arcturus and Alpha flamed up because of the only shattered glass?)
Fortunately, the solution was found in the Galactic Academy. For diplomats of the lower rank it is enough to learn just a single branch of history – the one that concerns only the cluster of star systems, in which he is going to work. (Diplomats of the lower rank negotiate only with planets that are located in one star cluster. How come we didn’t guess this earlier?)
Taking this very important observation into consideration, it was decided to replace a single intergalactic course with several separate courses, each covering only the part of history that refers to only one star cluster. Of course, it is necessary to learn history in chronological order, beginning from the origin of humanity. That’s why the history of the Earth needs to be included in all collections of separate histories. Then things become complicated: for example, emigrants from Centaurus system colonized the star system of Herdsman, so the textbook on the history of Herdsman system has to contain the early history of Centaurus system. In order to decide, in which textbooks which phases of history should be included, historians of Galactic Academy divided general intergalactic history into many small milestones. Then all milestones were combined into one big tree (omnipresent biologists helped historians in this work, as they had always been using these trees). The milestone referring to early history of the Earth (before the space colonization) was declared the root. Milestones referring to history of star systems close to solar system appear to be its sons (because these systems were colonized by emigrants from Earth) and so on. That’s all! To determine milestones that have to be included in a particular textbook it is only required to determine quickly, whether the milestone A is located in a subtree with the root in milestone B.

Input

In the first line there is a number N (N ≤ 40000), which defines the total number of milestones. In the next N lines there are descriptions of each milestone.
Each milestone is defined by two numbers: ID – an unique numerical identifier of a milestone and ParentID – identifier of the milestone which is its father in a tree. ParentID for the root equals to -1.
(N+2)^th line contains number L (L ≤ 40000) – amount of queries. The next L lines contain descriptions of queries: on each line there are two different numbers A and B. All identifiers lie between 0 and 40000.

Output

For each query it is necessary to write in separate line:

• 
  1, if milestone A is a root of subtree which contains milesone B.
  
• 
  2, if milestone B is a root of subtree which contains milesone A.
  
• 
  0, if no one of the first two conditions is true.
  

Sample