import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    static int N = 100010;
    static class Node{
        int val;//距离
        int pos;//位置
        Node next;//下一个节点

    }
    //存储邻接表的头节点
    static Node [] h = new Node[2*N];
    //visit数组
    static boolean [] visit = new boolean[2*N];

    //插入函数 到 u节点中插入一个新的节点 p
    static void insert(int u,int p){
        //头节点
        Node newNode = new Node(); newNode.pos = p;
        newNode.next = h[u].next;
        h[u].next = newNode;

    }

    //返回以u节点为根的数节点的个数
    static int dfstree(int u){
        visit[u] = true;
        int sum = 1;
        //头节点数目
        Node hh = h[u];
        while(hh.next!=null){
            hh = hh.next;
            if(!visit[hh.pos]){
                sum += dfstree(hh.pos);
            }
        }

        return sum;

    }
    //深度优先搜索
    static void dfs(int u){
        visit[u] = true;
        System.out.println(u);

        Node hh  =  h[u];
        //拓展能访问所有节点
        while(hh.next!=null){
            hh = hh.next;
            if(!visit[hh.pos]){
                dfs(hh.pos);
            }
        }
    }

    //宽度优先搜索 并输入当前访问的层数
    static void bfs(int u){

        Queue<Integer> q = new LinkedList<Integer>();
        q.add(u);
        visit[u] = true;

        int layer = 1;
        while(!q.isEmpty()){
            //出队
            int n = q.size();
            for(int i=0;i<n;i++){
                int f = q.poll();
                System.out.println("layer="+layer + "pos="+f);
                //邻接表队头
                Node hh = h[f];
                while(hh.next!=null){
                    hh = hh.next;
                    if(!visit[hh.pos]){
                        visit[hh.pos] = true;
                        q.add(hh.pos);
                    }
                }
            }
            layer++;
        }
    }

}