#include #include #include #include using namespace std; typedef vector edges; typedef map graph; map dijkstra( graph& G, int s, int cannot_enter=-1 ) { // one-to-all shortest path map shortest; shortest[s] = 0; vector Q(1,s); for(int d=1; !Q.empty(); ++d) { vector Q2; for(int i=0; i!=Q.size(); ++i) { edges& next = G[Q[i]]; for(int j=0; j!=next.size(); ++j) if( next[j]!=cannot_enter && !shortest.count(next[j]) ) shortest[next[j]]=d, Q2.push_back(next[j]); } Q.swap(Q2); } return shortest; } set bottle_neck( graph& G, int s, int e ) { // tooooooooooo naive solution. // for each node, just remove it and test whether we can go from s to e. // but the problem size is in fact small enough... :P set ans; for(graph::iterator it=G.begin(); it!=G.end(); ++it) if( it->first!=e && !dijkstra(G,s,it->first).count(e) ) ans.insert(it->first); return ans; } int main() { for(int n,m,I,J,E; cin>>n>>m,n|m;) { graph GI, GJ; // input the graph cin >> I >> J >> E; for(int r1,r2,e,i=0; i!=m; ++i) { cin >> r1 >> r2 >> e; GI[r1].push_back(r2); GI[r2].push_back(r1); GJ[r1].push_back(r2); if(e==0) GJ[r2].push_back(r1); } // solve and output set neck = bottle_neck(GI, I, E); map I_shortest = dijkstra(GI, I); map J_shortest = dijkstra(GJ, J); const char* ans = "ESCAPE"; for(set::iterator it=neck.begin(); it!=neck.end(); ++it) if( J_shortest.count(*it) && I_shortest.count(*it) && J_shortest[*it] < I_shortest[*it] ) { ans = "AMBUSHED"; break; } cout << ans << endl; } }