#1153977 (C++17) No.3482 Quod Erat Demonstrandum

• 問題: No.3482 Quod Erat Demonstrandum
• ユーザー: tanpaku
• 提出日時: 2026-03-27 21:38:37
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 14,700 bytes
• コンパイル時間: 6,907 ms
• コンパイル使用メモリ: 289,888 KB
• 実行使用メモリ: 22,168 KB
• 最終ジャッジ日時: 2026-03-27 21:39:27
• 合計ジャッジ時間: 12,479 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_1

ファイルパターン	結果
sample	AC * 1
other	AC * 27 WA * 18

ソースコード

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll=long long;
using ld=long double;
using uint=unsigned int;
using ull=unsigned long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
using vd=vector<double>;
using vvd=vector<vd>;
using vvvd=vector<vvd>;
using vld=vector<ld>;
using vvld=vector<vld>;
using vvvld=vector<vvld>;
using vc=vector<char>;
using vvc=vector<vc>;
using vvvc=vector<vvc>;
using vs=vector<string>;
using vvs=vector<vs>;
using vvvs=vector<vvs>;
using vl=vector<ll>;
using vvl=vector<vl>;
using vvvl=vector<vvl>;
using vb=vector<bool>;
using vvb=vector<vb>;
using vvvb=vector<vvb>;
using pi=pair<int,int>;
using vpi=vector<pi>;
using vvpi=vector<vpi>;
using vvvpi=vector<vvpi>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
using vvpl=vector<vpl>;
using vvvpl=vector<vvpl>;
using si=set<int>;
using vsi=vector<si>;
using vvsi=vector<vsi>;
using vvvsi=vector<vvsi>;
using sl=set<ll>;
using vsl=vector<sl>;
using vvsl=vector<vsl>;
using vvvsl=vector<vvsl>;
using ss=set<string>;
using svi=set<vi>;
using svvi=set<vvi>;
using svvvi=set<vvvi>;
using svl=set<vl>;
using svvl=set<vvl>;
using svvvl=set<vvvl>;
using svs=set<vs>;
using sb=set<bool>;
using spi=set<pi>;
using svpi=set<vpi>;
using svvpi=set<vvpi>;
using svvvpi=set<vvvpi>;
using spl=set<pl>;
using svpl=set<vpl>;
using svvpl=set<vvpl>;
using svvvpl=set<vvvpl>;
template <typename T> using PQ=priority_queue<T>;
template <typename T> using PQG=priority_queue<T,vector<T>,greater<T>>;
template <typename T> using uset=unordered_set<T>;
template <typename T> using mset=multiset<T>;
template <typename T> using umset=unordered_multiset<T>;
template <typename T, typename S> using umap=unordered_map<T,S>;
template <typename T, typename S> using mmap=multimap<T,S>;
template <typename T, typename S> using ummap=unordered_multimap<T,S>;

template<typename T>
void set_MOD(T a){
    atcoder::modint::set_mod(a);
}
using mint=atcoder::modint;
//using mint=modint998244353;
//using mint=modint1000000007;
using vm=vector<mint>;
using vvm=vector<vm>;
using vvvm=vector<vvm>;
using vvvvm=vector<vvvm>; 

#define each(i,...) for(auto&& i:__VA_ARGS__)
#define each2(i,j,...) for(auto&& [i,j]:__VA_ARGS__)
#define rep(i, n) for (ll i = 0; i < (int)(n); i++)
#define rep2(i,s,n) for (ll i = (s); i < (int)(n); i++) 
#define rep3(i,n) for (ll i = 1; i <= (int)(n); i++)
#define rep4(i,n) for (ll i = (int)(n)-1;i >= 0;i--)
#define Yes(a) cout<<(a?"Yes":"No")<<"\n"
#define YES(a) cout<<(a?"YES":"NO")<<"\n"
#define Takahashi(a) cout<<(a?"Takahashi":"Aoki")<<"\n"
#define Alice(a) cout<<(a?"Alice":"Bob")<<"\n"
#define First(a) cout<<(a?"First":"Second")<<"\n"
#define Possible(a) cout<<(a?"Possible":"Impossible")<<"\n"
#define which(a,s,t) cout<<(a?s:t)<<"\n"
#define fls flush(cout)
#define fix(a) cout<<fixed<<setprecision(a)
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define em emplace
#define ef emplace_front
#define eb emplace_back
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define SORT(v) sort(all(v))
#define RSORT(v) sort(rall(v))
#define REV(v) reverse(all(v))
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
template <typename T=ll,typename S> T SUM(const S &v){return accumulate(all(v),T(0));}
#define SZ(v) (ll)(v.size())
#define UNIQ(v) v.erase(unique(all(v),v.end()))
template <typename T, typename S> bool chmax(T &a, const S &b){return(a<b?a=b,1:0);}
template <typename T, typename S> bool chmin(T &a, const S &b){return(a>b?a=b,1:0);}

#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define INTD(...) int __VA_ARGS__;in2(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define LLD(...) ll __VA_ARGS__;in2(__VA_ARGS__)
#define ULL(...) ull __VA_ARGS__;in(__VA_ARGS__)
#define ULLD(...) ull __VA_ARGS__;in2(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;in(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;in(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__;in(__VA_ARGS__)
#define VI(name,size) vi name(size);in(name)
#define VID(name,size) vi name(size);in2(name)
#define VL(name,size) vl name(size);in(name)
#define VLD(name,size) vl name(size);in2(name)
#define VS(name,size) vs name(size);in(name)
#define VEC(type,name,size) vector<type> name(size);in(name)
#define VV(type,name,h,w) vector<vector<type>> name(h,vector<type>(w));in(name)

template <typename T, typename S> pair<T,S> &operator++(pair<T,S> &p){p.fi++;p.se++;return p;}
template <typename T, typename S> pair<T,S> operator++(pair<T,S> &p, int){auto r=p;p.fi++;p.se++;return r;}
template <typename T, typename S> pair<T,S> &operator--(pair<T,S> &p){p.fi--;p.se--;return p;}
template <typename T, typename S> pair<T,S> operator--(pair<T,S> &p, int){auto r=p;p.fi--;p.se--;return r;}
    
template <typename T> vector<T> &operator++(vector<T> &v){for(auto&& a:v)a++;return v;}
template <typename T> vector<T> operator++(vector<T> &v,int){auto r=v;for(auto&& a:v)a++;return r;}
template <typename T> vector<T> &operator--(vector<T> &v){for(auto&& a:v)a--;return v;}
template <typename T> vector<T> operator--(vector<T> &v,int){auto r=v;for(auto&& a:v)a--;return r;}

namespace io
{
inline void scan(){}
inline void scan(int &a){cin>>a;}
inline void scan(ll &a){cin>>a;}
inline void scan(uint &a){cin>>a;}
inline void scan(ull &a){cin>>a;}
inline void scan(char &a){cin>>a;}
inline void scan(string &a){cin>>a;}
inline void scan(float &a){cin>>a;}
inline void scan(double &a){cin>>a;}
inline void scan(ld &a){cin>>a;}
inline void scan(mint &a){
    ll b;scan(b);
    a=b;
}
inline void scan(vb &v){
    rep(i,v.size()){
        int a;
        scan(a);
        v[i]=a;
    }
}
template<typename T>
inline void scan(vector<T> &v);
template<typename T,size_t size>
inline void scan(array<T,size> &v);
template<typename T,typename S>
inline void scan(pair<T,S> &p);
template<typename T,size_t size>
inline void scan(T (&v)[size]);
template<typename T>
inline void scan(vector<T> &v){for(auto &a:v)scan(a);}
template<typename T>
inline void scan(deque<T> &v){for(auto &a:v)scan(a);}
template<typename T,size_t size>
inline void scan(array<T,size> &v){for(auto &a:v)scan(a);}
template<typename T,typename S>
inline void scan(pair<T,S> &p){scan(p.fi);scan(p.se);}
template<typename T,size_t size>
inline void scan(T (&v)[size]){for(auto &a:v)scan(a);}
template<typename T>
inline void scan(T &a){cin>>a;}
inline void in(){}
inline void in2(){}
template<typename F,typename...B>
inline void in(F &f,B &...b){
    scan(f);
    in(b...);
}
template<typename F,typename...B>
inline void in2(F &f,B &...b){
    scan(f);
    --f;
    in2(b...);
}
inline void print(){cout<<" ";}
inline void print(const bool &a){cout<<a;}
inline void print(const int &a){cout<<a;}
inline void print(const ll &a){cout<<a;}
inline void print(const uint &a){cout<<a;}
inline void print(const ull &a){cout<<a;}
inline void print(const char &a){cout<<a;}
inline void print(const char a[]){cout<<a;}
inline void print(const string &a){cout<<a;}
inline void print(const float &a){cout<<a;}
inline void print(const double &a){cout<<a;}
inline void print(const ld &a){cout<<a;}
inline void print(const mint &a){cout<<a.val();}
template<typename T>
inline void print(const vector<T> &v);
template<typename T,size_t size>
inline void print(const array<T,size> &v);
template<typename T,typename S>
inline void print(const pair<T,S> &p);
template<typename T,size_t size>
inline void print(const T (&v)[size]);
template<typename T>
inline void print(const vector<T> &v){
    if(v.empty())return;
    print(v[0]);
    for(auto i=v.begin();++i!=v.end();){
        cout<<' ';
        print(*i);
    }
}
template<typename T>
inline void print(const deque<T> &v){
    if(v.empty())return;
    print(v[0]);
    for(auto i=v.begin();++i!=v.end();){
        cout<<' ';
        print(*i);
    }
}
template<typename T,size_t size>
inline void print(const array<T,size> &v){
    print (v[0]);
    for(auto i=v.begin();++i!=v.end();){
        cout<<' ';
        print(*i);
    }
}
template<typename T,typename S>
inline void print(const pair<T,S> &p){print(p.fi);print();print(p.se);}
template<typename T,size_t size>
inline void print(const T (&v)[size]){
    print(v[0]);
    for(auto i=v;++i!=end(v);){
        cout<<' ';
        print(*i);
    }
}
template<typename T>
inline void print(const T &a){cout<<a;}
inline void out(){cout<<"\n";}
inline void out2(){cout<<"\n";}
template<typename T>
inline void out(const T &t){
    print (t);
    cout<<"\n";
}
template<typename T>
inline void out2(T &t){
    ++t;
    out(t);
}
template <typename F,typename...B>
inline void out(const F &f,const B &...b){
    print(f);
    cout<<' ';
    out(b...);
}
template <typename F,typename...B>
inline void out2(F &f,B &...b){
    ++f;
    print(f);
    cout<<' ';
    out2(b...);
}
struct IOsetup{
    IOsetup(){
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        std::cout << std::fixed << std::setprecision(16);
    }
}iosetup;
}
using namespace io;



template<typename T> using fentree=fenwick_tree<T>;
const int INF=1<<30;
const ll LINF=1LL<<60;
const ld EPS=1e-9;
const ld Pi=3.141592653589793238;
const int dx[8]={0,1,0,-1,-1,-1,1,1};
const int dy[8]={1,0,-1,0,-1,1,-1,1};

namespace my_grids
{
    bool outgrid(int x,int y,int H,int W){
        return !(0<=x&&x<H&&0<=y&&y<W);
    }
}
using namespace my_grids;

namespace my_numbers
{
    long long modpow(ll a,ll n,ll p){//O(log N) each query
        if(p==-1)return n!=0?modpow(a*a,n/2,p)*(n%2==1?a:1):1;
        return n!=0?modpow(a*a%p,n/2,p)*(n%2==1?a:1)%p:1;
    }
    bool miller_rabin(ll n){//O(log N) each query
        if(n%2==0)return n==2;
        ll q=n-1,Q=0;
        for(;q%2==0;Q++)q/=2;
        ll check[7]={2, 325, 9375, 28178, 450775, 9780504, 1795265022};
        each(a,check){
            if(n<=a)return true;
            ll x=modpow(a,q,n),i=0;
            if(x!=1){
                for(;i<Q;i++){
                    if(x==n-1)break;
                    x=__int128_t(x)*x%n;
                }
                if(i==Q)return false;
            }
        }
        return false;
    }
    bool is_prime(ll n){//O(N) every query
        if(n<=1) return false;
        for(ll p=2;p*p<=n;p++)if(n%p==0)return false;
        return true;
    }
    vector<bool> prime_table(ll a){//O(N log log N)
        vb prime(a+1,true);
        if(a>=0)prime[0]=false;
        if(a>=1)prime[1]=false;
        for(int i=2;i*i<=a;i++){
            if(!prime[i])continue;
            for(int j=i+i;j<=a;j+=i){
                prime[j]=false;
            }
        }
        return prime;
    }
    vector<ll> divisor(ll a){//O(N) every query
        vl rtn(0);
        vl big(0);
        for(ll i=1;i*i<=a;i++){
            if(a%i!=0)continue;
            rtn.pb(i);
            if(i*i!=a)big.pb(a/i);
        }
        while(big.size()){
            rtn.pb(big.back());
            big.ppb();
        }
        return rtn;
    }
    vector<pair<ll,ll>> prime_factorize(ll a){//O(N) every query
        vpl rtn(0);
        for(ll p=2;p*p<=a;p++){
            if(a%p!=0)continue;
            int num=0;
            while(a%p==0){
                num++;
                a/=p;
            }
            rtn.pb({p,num});
        }
        if(a!=1)rtn.pb({a,1});
        return rtn;
    }
    template <typename T>
    T extgcd(T a,T b,T &x,T &y){//O(log N), ax+by=gcd(a,b)
        T d=a;
        if(b!=0){
            d=extgcd(b,a%b,y,x);
            y-=(a/b)*x;
        }else{
            x=1;
            y=0;
        }
        return d;
    }
    namespace mintnCk{
        const int nCkmax=5000000;
        vector<mint> fac(0),finv(0),inv(0);
        void nCkinit(){
            const ll mod=mint::mod();
            fac.resize(nCkmax,0);
            finv.resize(nCkmax,0);
            inv.resize(nCkmax,0);
            fac[0]=fac[1]=1;
            finv[0]=finv[1]=1;
            inv[1]=1;
            rep2(i,2,nCkmax){
                fac[i]=fac[i-1]*i;
                inv[i]=mod-inv[mod%i]*(mod/i);
                finv[i]=finv[i-1]*inv[i];
            }
        }
        template<typename T,typename S>
        mint nCk(T n,S k){
            if(n<k)return 0;
            if(n<0||k<0)return 0;
            return fac[n]*finv[k]*finv[n-k];
        }
    }
    void usemintnCk(){
        using namespace mintnCk;
        nCkinit();
    }
    namespace intnCk{
        ll mod;
        const int nCkmax=5000000;
        vector<ll> fac(0),finv(0),inv(0);
        template<typename T>
        void nCkinit(T a){
            mod=a;
            fac.resize(nCkmax,0);
            finv.resize(nCkmax,0);
            inv.resize(nCkmax,0);
            fac[0]=fac[1]=1;
            finv[0]=finv[1]=1;
            inv[1]=1;
            for(int i=2;i<nCkmax;i++){
                fac[i]=fac[i-1]*i%mod;
                inv[i]=mod-inv[mod%i]*(mod/i)%mod;
                finv[i]=finv[i-1]*inv[i]%mod;
            }
        }
        template<typename T,typename S>
        ll nCk(T n,S k){
            if(n<k)return 0;
            if(n<0||k<0)return 0;
            return fac[n]*(finv[k]*finv[n-k]%mod)%mod;
        }
    }
    template<typename T> void useintnCk(T a){
        using namespace intnCk;
        nCkinit(a);
    }
}
using namespace my_numbers;

void solve(){
    INT(N,M);
    vvi ok(N),ng(N);
    rep(i,M){
        INTD(A,B,C);
        if(C==0){
            ok[A].pb(B);
            ok[B].pb(A);
        }else{
            ng[A].pb(B);
            ng[B].pb(A);
        }
    }
    queue<int> q;q.em(0);
    vi distok(N,-1);distok[0]=0;
    while(q.size()){
        int now=q.front();q.pop();
        each(i,ok[now]){
            if(distok[i]==-1){
                distok[i]=distok[now]+1;
                q.em(i);
            }
        }
    }
    q.em(N-1);
    vi distng(N,-1);distng[N-1]=0;
    while(q.size()){
        int now=q.front();q.pop();
        each(i,ng[now]){
            if(distng[i]==-1){
                distng[i]=distng[now]+1;
                q.em(i);
            }
        }
    }
    bool ac=false,wa=false;
    int ans=INF;
    rep(i,N){
        if(distok[i]!=-1&&distng[i]!=-1){
            wa=true;
            chmin(ans,distok[i]+distng[i]);
        }
    }
    if(distok[N-1]!=-1)ac=true,chmin(ans,distok[N-1]);
    if(distng[0]!=-1)wa=true,chmin(ans,distng[0]);
    if(ac){
        out("Same");
        out(ans);
    }else if(wa){
        out("Different");
        out(ans);
    }else{
        out("Unknown");
    }
}

int main(){
    set_MOD(1000000007);
    set_MOD(998244353);
    int T=1;
    in(T);
    while(T--)solve();  
}