void dfs(int u)
{
    st[u] = true;
    printf("%d ",u);

    for(auto p = head[u]; p; p = p->next){
        int j = p->id;
        if(!st[j]) dfs(j);
    }

}

void bfs()
{
    queue<int> q;
    st[1] = true;
    q.push(1);

    while(q.size()){
        auto t = q.front();
        q.pop();
        printf("%d ",t);
        for(auto p = head[t]; p; p=p->next){
            int j = p->id;
            if(!st[j]){

                st[j] = true;
                q.push(j);
            }
        }

    }
}