#include #include #include #include using namespace std; // 最大公約数:ユークリッドの互除法 int gcd( int x, int y ) { int t; while( x ) t=x, x=y%x, y=t; return y; } // なにかしら無向グラフの連結性を判定できる道具: // UnionFindなど使ってみる。普通にDFSなりなんなりでもいい。 class UnionFind { public: void conn(int x, int y) { repr_conn( repr(x), repr(y) ); } int size_of(int x) { return size[repr(x)]+1; } private: map link, size; int repr(int x) { while( link.count(x) ) x = link[x]; return x; } void repr_conn( int x, int y ) { if( x == y ) return; if( size[x] < size[y] ) { link[y] = x; size[x]+= size[y]+1; } else { link[x] = y; size[y]+= size[x]+1; } } }; // 辺: 有向で扱うのでpairの順番に注意 typedef pair edge; // アリ滞在情報 struct stay_t { int AntID; // アリ番号 int q, r; // 点or辺の出発頂点 に t = qk+r の時にいる }; // 二匹のアリは点上で出会うか? bool pt_crosses( stay_t s, stay_t t ) { return abs(s.r-t.r) % gcd(s.q,t.q) == 0; } // 二匹のアリは辺上ですれ違うか? bool eg_crosses( stay_t s, stay_t t, int len ) { // 進行方向が逆なので、「同時に辺上に存在している時点がある」ことを // 確かめればOK。つまり、 // [s.r, s.r+len]+s.q*x と [t.r, t.r+len]+t.q*y // が重なりうるかどうか判定。 int g = gcd(s.q,t.q); int a = abs(t.r-s.r); // [0,len] [a,a+len] をgcdずつずらして重ねられればOK return (a <= len+a/g*g || (a/g+1)*g <= a+len); } int main() { int nCase = 0; for(int n,m,a; cin>>n>>m>>a,n|m|a; ) // n:頂点数, m:辺数, a:アリ数 { assert( 0<=n && n<100 ); assert( 0<=m && m<100 ); assert( 0<=a && a<100 ); // 辺の長さ情報を取得 map length; for(int i=0; i!=m; ++i) { int x, y, t; cin>>x>>y>>t; assert( 1<=x && x<=n ); assert( 1<=y && y<=n ); length[edge(x,y)] = length[edge(y,x)] = t; } // 各アリの滞在情報を取得 map< int, vector > pt_stay; // 点 map > eg_stay; // 辺 for(int i=0; i!=a; ++i) { // 経路情報を読み込み vector path; for(int p; cin>>p,p; ) { assert( 1<=p && p<=n ); path.push_back(p); } assert( path.size() < 100 ); path.push_back(path[0]); // 一周の長さを計算 int loopLength = 0; for(int j=0; j+1 >::iterator it=pt_stay.begin(); it!=pt_stay.end(); ++it ) { const vector& st = it->second; for(int i=0; i!=st.size(); ++i) for(int j=i+1; j!=st.size(); ++j) if( pt_crosses(st[i], st[j]) ) uf.conn( st[i].AntID, st[j].AntID ); } // 各辺ごとに、アリ同士がすれ違う可能性があるかどうか判定 for(map >::iterator it=eg_stay.begin(); it!=eg_stay.end(); ++it ) { const vector& st = it->second; const vector& st2 = eg_stay[edge(it->first.second,it->first.first)]; for(int i=0; i!=st.size(); ++i) // 今のedgeにstayするアリ for(int j=0; j!=st2.size(); ++j) // 逆向きにstayするアリ if( eg_crosses(st[i], st2[j], length[it->first]) ) uf.conn( st[i].AntID, st2[j].AntID ); } // 全員が同じ通信網に入ってるか? bool ok = (uf.size_of(1)==a); // 解答出力 cout << "Revolution #" << ++nCase << endl; cout << "Revolution " << (ok ? "can start." : "fails.") << endl; cout << endl; } }