Guest User

Untitled

a guest
Aug 15th, 2017
86
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. int input(){
  5.     int res = 0; char c = ' ';
  6.     while (c < '0') c = getchar();
  7.     while (c >= '0') res = res * 10 + (c - '0'), c = getchar();
  8.     return res;
  9. }
  10. const int N = 1e5 + 1;
  11.  
  12. int dst[N];
  13. vector <int> g[2][N];
  14. int main(){
  15.     int n = input(), m = input(), t = input();
  16.     for (int i = 0; i < m; ++ i){
  17.         int u = input() - 1, v = input() - 1;
  18.         g[0][u].push_back(v), g[1][v].push_back(u);
  19.     }
  20.     for (int i = 1; i < n; ++ i) dst[i] = 2e9;
  21.     queue <pair <int, int> > q;
  22.     q.push({0, 0});
  23.     while (q.size()){
  24.         int v = q.front().first, d = q.front().second;
  25.         q.pop();
  26.         for (auto u : g[d & 1][v])
  27.             if (dst[u] == 2e9)
  28.                 q.push({u, dst[u] = d + 1});
  29.         for (auto u : g[~d & 1][v])
  30.             if (dst[u] == 2e9){
  31.                 q.push({v, d + 1});
  32.                 break;
  33.             }
  34.     }
  35.     for (int i = 0; i < t; ++ i)
  36.         cout << (dst[n - 1] <= input() ? "GGMU" : "FML") << "\n";
  37. }
RAW Paste Data Copied