void BFS(vector<vector<TreeNode *>> &cash, vector<TreeNode *> level) {
     int len = level.size();
     if (len == 0) return;
     vector<TreeNode *> childs;
     for (int i = 0; i < len; ++i) {
         if (level[i]->left) childs.push_back(level[i]->left);
         if (level[i]->right) childs.push_back(level[i]->right);
     }
     if (childs.size() > 0) cash.push_back(childs);
     BFS(cash, childs);
 }

void BFSTraversal(graph *g)
{
	int visited[g->v];
	for(int i=0;i<g->v;i++)
	  visited[i]=0;
	for(int i=0;i<g->v;i++)
	{
		if(!visited[i])
		  BFS(g,i,visited);
	} 
}

void BFS_All(AdjList *a)
{
    int i;
    for(i=0;i<a->vexnum;i++)
    {
        if(!a->vertex[i].sign)
        {
            BFS(a,i);
        }
    }
}

//gap filling
void GapFiller::fill() {
    LOG4CXX_DEBUG(logger, "Begin Gap Filling ... ");

    size_t num_failed_gaps = 0, num_uniq_gaps = 0, num_multi_gaps = 0, num_overlaps = 0;
	for (size_t i = 0; i < _scaffolds.size(); ++i) {
		if (_scaffolds[i].contigs.size() <= 1) { // no gaps
			continue;
		}
        Component::ContigIdList contigs = _scaffolds[i].contigs;

		for (size_t j = 1; j < contigs.size(); ++j) {
			int left_index = contigs[j - 1];
			int right_index = contigs[j];

            const std::string& lsequence = _uniq_graph._indexer[left_index].seq;
            const std::string& rsequence = _uniq_graph._indexer[right_index].seq;
            std::string suffix = lsequence.substr(lsequence.length() - (_K - 1), _K - 1);
            std::string prefix = rsequence.substr(0, _K - 1);

			int overlap = alignment(suffix, prefix);
            int gap = _scaffolds[i].gaps[j - 1];
			if (overlap >= _OVERLAP) {
                _gapinfo_tbl[std::make_pair(i, j)] = GapInfo(-1, -overlap);
                ++num_overlaps;
			} else if (gap > _INSERT_SIZE + 3*_DELTA) {
                _gapinfo_tbl[std::make_pair(i, j)] = GapInfo(-1, gap);
                ++num_failed_gaps;
            } else {
                try {
                    GapInfo gapinfo(-1, gap);
                    BFS(left_index, right_index, gap, &gapinfo);
                    _gapinfo_tbl[std::make_pair(i, j)] = gapinfo;
                    if (gapinfo.pathlist.empty()) {
                        ++num_failed_gaps;
                    } else if (gapinfo.pathlist.size() == 1) {
                        ++num_uniq_gaps;
                    } else {
                        ++num_multi_gaps;
                    }
                } catch(std::bad_alloc) {
                    LOG4CXX_WARN(logger, "BFS is too memory-intensive, ignoring...");
                    _gapinfo_tbl[std::make_pair(i, j)] = GapInfo(-1, -gap);
                    ++num_failed_gaps;
                }
            }
		}
	}
	LOG4CXX_DEBUG(logger, boost::format("The number of gaps = %d") % _gapinfo_tbl.size());
	LOG4CXX_DEBUG(logger, boost::format("The number of failed gaps = %d") % num_failed_gaps);
	LOG4CXX_DEBUG(logger, boost::format("The number of unique gaps = %d") % num_uniq_gaps);
	LOG4CXX_DEBUG(logger, boost::format("The number of multiple gaps = %d") % num_multi_gaps);
	LOG4CXX_DEBUG(logger, boost::format("The number of overlap = %d") % num_overlaps);
}

 int numIslands(vector<vector<char>>& grid) {
     const int m = grid.size(), n = grid[0].size();
     int ret = 0;
     for(int i = 0; i < m; ++i)
     	for(int j = 0; j < n; ++j) {
     		if(1 == grid[i][j]) {
     			++ret;
     			BFS(grid, i, j);
     		}
     	}
 	return ret;
 }

task main()
{
	Queue Q;
	CreateEmpty(&Q);
	int color = searchSpot();
	if(color==green) {
		stepAhead(220);
		turn(right,20);
		cekSimpang(&Q);
	}
	BFS(first,&Q);
}

int isap(int st, int ed, int N) {
    BFS(st, ed);
    memcpy(cur, head, sizeof(head));
    int top = 0;
    int u = st;
    int ans = 0;
    while(dep[st] < N) {
        if(u == ed) {
            int Min = INF;
            int inser;
            for(int i = 0; i < top; i++)
                if(Min > edge[S[i]].cap - edge[S[i]].flow) {
                    Min = edge[S[i]].cap - edge[S[i]].flow;
                    inser = i;
                }
            for(int i = 0; i < top; i++) {
                edge[S[i]].flow += Min;
                edge[S[i] ^ 1].flow -= Min;
            }
            ans += Min;
            top = inser;
            u = edge[S[top] ^ 1].to;
            continue;
        }
        bool flag = false;
        int v;
        for(int i = cur[u]; i != -1; i = edge[i].next) {
            v = edge[i].to;
            if(edge[i].cap - edge[i].flow && dep[v] + 1 == dep[u]) {
                flag = true;
                cur[u] = i;
                break;
            }
        }
        if(flag) {
            S[top++] = cur[u];
            u = v;
            continue;
        }
        int Min = N;
        for(int i = head[u]; i != -1; i = edge[i].next)
            if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min) {
                Min = dep[edge[i].to];
                cur[u] = i;
            }
        gap[dep[u]]--;
        if(!gap[dep[u]])return ans;
        dep[u] = Min + 1;
        gap[dep[u]]++;
        if(u != st) u = edge[S[--top] ^ 1].to;
    }
    return ans;
}

int main()
{
	//Algorithms::testQuickSort();
	//Algorithms::testCountingSort();
	//Algorithms::lis();
	//Algorithms::editDistance();
	//Algorithms::pocket();
	//Algorithms::uniquePocket();
	DFS();
	BFS();
	return 0;
}

int main()
{
    
    LinkGraph **g = Create_Graph_List();

    Input_Graph_Edge(g);

    Print_Graph_List(g);

    BFS(g,0);
    return 0;
}

    static GRA_tpCondRet ExcluirAresta (GRA_tppGrafo grafo, tpVertice* v, tpVertice* u) {
        RemoverAresta(v, u);//mexe só em v, ou deveria       
        RemoverAresta(u, v);

        //BFS pra detectar se é necessário gerar nova componente.
        if (BFS(v,u) != 1) { //Estão em componentes distintas
            if (LIS_InserirElementoApos(grafo->componentes, u) != LIS_CondRetOK) {
                return GRA_CondRetFaltouMemoria;
            }
        }
        return GRA_CondRetOK;
    }   

bool feasible_placement (std::vector<GraphNode>& nodes)
{
    for (auto& node: nodes) {
        if (node.d == -1) {
            node.d = 0;
            if (!BFS(&node)) {
                return false;
            }
        }
    }
    return true;
}

int main()
{
    for(int i=0; i<8; i++)
    {
        fscanf(fin,"%d",&target[i]);
        target[i]--;
    }
    init();
    BFS();
    output();
    return 0;
}

void solve(unsigned start, unsigned end)
{ unsigned k;
  for (k = 0; k < n; k++) { used[k] = 0; pred[k] = -1; }
  BFS(start);
  if (pred[end] > -1) {
    printf("Намереният път е: \n");
    printf("\nДължината на пътя е %u\n", printPath(end));
  }
  else {
    printf("Път между двата върха не съществува! \n");
  }
}

int main()
{
   // freopen("xxxx.in", "r", stdin);
    //freopen("xxxx.out", "w",stdout);
    while (scanf("%d %d", &m, &n) == 2){
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j){
                scanf("%d", &map[i][j]);
            }
        startHP = map[0][0];
        map[0][0] = 0;
        tot = 0;
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (map[i][j] > 0){
                    X[tot] = i, Y[tot] = j, getHP[tot] = map[i][j];
                    idx[i][j] = tot++;
                }
                else idx[i][j] = -1;
        X[tot] = 0, Y[tot] = 0;
        if (idx[0][0] == -1) idx[0][0] = tot;
        ++tot;
        X[tot] = m-1, Y[tot] = n-1;
        if (idx[m-1][n-1] == -1) idx[m-1][n-1] = tot;
        ++tot;
        for (int i = 0; i < tot; ++i) BFS(X[i], Y[i], dis[i]);
        tot-=2;
        int max = 1<<tot;
        for (int i = 0; i < tot; ++i)
            for (int j = 0; j < max; ++j)
                f[i][j] = -1;
        for (int i = 0; i < tot; ++i)
            if (startHP >= dis[tot][i])
                f[i][1<<i] = startHP-dis[tot][i]+getHP[i];
        int ans = -1;
        if (ans < startHP - dis[tot][tot+1]) ans = startHP-dis[tot][tot+1];
        for (int k = 0; k < max; ++k)
            for (int i = 0; i < tot; ++i){
                if (f[i][k] < 0) continue;
                int tmp = f[i][k] - dis[i][tot+1];
                if (tmp > ans) ans = tmp;
                for (int j = 0, test = 1; j < tot; ++j, test <<= 1){
                    if (k & test) continue;
                    if (f[i][k] - dis[i][j] >= 0 && f[j][k|test] < f[i][k]-dis[i][j]+getHP[j])
                        f[j][k|test] = f[i][k]-dis[i][j]+getHP[j];
                }
            }
        if (ans == -1) puts("you loss!");
        else printf("%d\n", ans);
    }
    return 0;
}

void BFSTraversal(graph *p){
	int node_num = p->node_num;
	int i;
	for(i = 0; i < node_num; i++){
		visited[i] = 0;
	}
	for(i = 0; i < node_num; i++){
		if(visited[i]==0){
			BFS(p, i);
		}
	}
	printf("\n");
}

void Benchmark::calculate(Implementation Type) {
	switch(Type){
	case bfs:
		BFS(&benchGraph, rand() % Vertices, rand() % Vertices);
		break;
	case dfs:
		DFS(&benchGraph, rand() % Vertices, rand() % Vertices);
		break;
	case astar:
		AStar(&benchGraph, rand() % Vertices, rand() % Vertices, Side);
		break;
	}
}

void main()
{
    Graph* pG;

    // 自定义"图"(输入矩阵队列)
    //pG = create_graph();
    // 采用已有的"图"
    pG = create_example_graph();

    print_graph(*pG);       // 打印图
    DFSTraverse(*pG);       // 深度优先遍历
    BFS(*pG);               // 广度优先遍历
}

int main(){
	scanf("%d%d",&n,&m);
	AdjacentMatrix.Size = n;
	for(int i = 0; i < m; i++){
		int start,end;
		scanf("%d%d",&start,&end);
		CreatePath(start,end);
		CreatePath(end,start);
	}
	int ans = BFS(n);
	printf("%d\n",ans);
	return 0;
}

int main () 
{
	/* change this number to generate different graphs */
	int graphTestNumber = 5; /* permissible values are 1-5 */
	/* switch this to 0 to use BFS */
	int useDFS = 0;
	
	int i, j;
	Graph g;
	
	/* set up the graph */
	if(graphTestNumber == 1)
		createGraph1(&g);
	else if(graphTestNumber == 2)
		createGraph2(&g);
	else if(graphTestNumber == 3)
		createGraph3(&g);
	else if(graphTestNumber == 4)
		createGraph4(&g);
	else if(graphTestNumber == 5)
		createGraph5(&g);
	else
	{
		printf("Invalid test number... Quitting");
		return 1;
	}
	printGraph(&g);
	
	if(useDFS)
		printf("\nComputing reachability using DFS\n");
	else
		printf("\nComputing reachability using BFS\n");

	for(i = 0; i < g.numVertices; ++i)
		for(j = i+1; j < g.numVertices; ++j)
		{			
			printf("%c to %c\t\t\t", g.vertexSet[i].label, g.vertexSet[j].label);
			if(useDFS)
				if(DFS(&g, &g.vertexSet[i], &g.vertexSet[j]))
					printf("reachable!\n");
				else
					printf("***UNREACHABLE***\n");
			else
				if(BFS(&g, &g.vertexSet[i], &g.vertexSet[j]))
					printf("reachable!\n");
				else
					printf("***UNREACHABLE***\n");
		}

	return 0;
}

int main()
{
    int Case, R, C;
    scanf("%d", &Case);

    while (Case--)
    {
        scanf("%d%d", &R, &C);

        //init
        int i;
        for (i = 0; i <= R; i++)
            for (int j = 0; j <= C; j++)
                path[i][j] = 0;
        while (!manQ.empty())
            manQ.pop();
        while (!fireQ.empty())
            fireQ.pop();

        //input
        for (int i = 1; i <= R; i++)
        {
            getchar();
            for (int j = 1; j <= C; j++)
            {
                maze[i][j] = getchar();
                if (maze[i][j] == 'F')
                {
                    fireQ.push(Coord(i, j));
                    path[i][j] = -1;
                }
                else if (maze[i][j] == '#')
                    path[i][j] = -1;
                else if (maze[i][j] == 'J')
                {
                    manQ.push(Coord(i, j));
                    path[i][j] = 1;
                }
            }
        }

        int ans = BFS(R, C);
        if (ans == -1)
            puts("IMPOSSIBLE");
        else
            printf("%d\n", ans);
    }

    return 0;
}