8-Laboratoriya ishi Mavzu: Kenglik bo’yicha izlash algoritmi(bfs)

Input
Output
1	4 5 1 4 1 3 3 2 2 4 2 1 2 3	2
2	4 4 2 3 2 1 2 4 4 3 1 3	2

2-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

3-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

4-topshiriq
Vladislav Isenbaev is a two-time champion of Ural, vice champion of TopCoder Open 2009, and absolute champion of ACM ICPC 2009. In the time you will spend reading this problem statement Vladislav would have solved a problem. Maybe, even two…
Since Vladislav Isenbaev graduated from the Specialized Educational and Scientific Center at Ural State University, many of the former and present contestants at USU have known him for quite a few years. Some of them are proud to say that they either played in the same team with him or played in the same team with one of his teammates…
Let us define Isenbaev's number as follows. This number for Vladislav himself is 0. For people who played in the same team with him, the number is 1. For people who weren't his teammates but played in the same team with one or more of his teammates, the number is 2, and so on. Your task is to automate the process of calculating Isenbaev's numbers so that each contestant at USU would know their proximity to the ACM ICPC champion.

Input

The first line contains the number of teams n (1 ≤ n ≤ 100). In each of the following n lines you are given the names of the three members of the corresponding team. The names are separated with a space. Each name is a nonempty line consisting of English letters, and its length is at most 20 symbols. The first letter of a name is capital and the other letters are lowercase.

Output

For each contestant mentioned in the input data output a line with their name and Isenbaev's number. If the number is undefined, output “undefined” instead of it. The contestants must be ordered lexicographically.

Sample