//#include <bits/stdc++.h>
#include <iostream>
#include <unordered_map>
#include <queue>

#define maxn 605
#define for_(i,a,b) \
        for (int i = (a); i < (b); i++)
#define INF 0x3f3f3f3f

using namespace std;

int n,m;

unordered_map<int,int> G[maxn];
int type[maxn];
int dist[maxn];
bool vis[maxn];

void init() {
    for_(i, 0, maxn) G[i].clear();
    memset(type, 0, sizeof(type));
    memset(dist, 0x3f, sizeof(dist));
    memset(vis, false, sizeof(vis));
}

void spfa() {
    queue<int> qu;
    qu.push(1); 
    dist[1] = 0;
    vis[1] = true;
    while (!qu.empty()) {
        auto t = qu.front();qu.pop();
        vis[t] = false;
        for (auto&...