1 /**************************************************************  2     Problem: 2199  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:160 ms  7     Memory:884 kb  8 ****************************************************************/  9   10 #include <cstdio> 11 #include <cstring> 12 #include <algorithm> 13   14 using namespace std; 15 const char ch[3] = {‘?‘, ‘N‘, ‘Y‘}; 16 const int N = 2005; 17 const int M = N << 2; 18   19 struct edge { 20   int next, to; 21   edge() {} 22   edge(int _n, int _t) : next(_n), to(_t) {} 23 } e[M]; 24   25 int n, m; 26 int first[N], tot; 27 bool vis[N]; 28 int ans[N]; 29   30 int read() { 31   int x = 0; 32   char ch = getchar(); 33   while (ch < ‘0‘ || ‘9‘ < ch) 34     ch = getchar(); 35   while (‘0‘ <= ch && ch <= ‘9‘) 36     (x *= 10) += ch - ‘0‘, ch = getchar(); 37   return x; 38 } 39   40 int get() { 41   int x = read(); 42   char ch = getchar(); 43   while (ch != ‘Y‘ && ch != ‘N‘) 44     ch = getchar(); 45   if (ch == ‘Y‘) --(x <<= 1); 46   else x <<= 1; 47   return x; 48 } 49   50 void add_edge(int x, int y) { 51   e[++tot] = edge(first[x], y); 52   first[x] = tot; 53 } 54   55 #define y e[x].to 56 void dfs(int p) { 57   int x; 58   vis[p] = 1; 59   for (x = first[p]; x; x = e[x].next) 60     if (!vis[y]) dfs(y); 61 } 62 #undef y 63   64 bool check(int p) { 65   int i; 66   memset(vis, 0, sizeof(vis)); 67   dfs(p); 68   for (i = 1; i <= n; ++i) 69     if (vis[2 * i] && vis[2 * i - 1]) return 0; 70   return 1; 71 } 72                   73   74 int main() { 75   int i, a, b, c, d, p, q; 76   n = read(), m = read(); 77   for (i = 1; i <= m; ++i) { 78     a = get(), c = get(); 79     if (a & 1) b = a + 1; 80     else b = a - 1; 81     if (c & 1) d = c + 1; 82     else d = c - 1; 83     add_edge(b, c); 84     add_edge(d, a); 85   } 86   for (i = 1; i <= n; ++i) { 87     p = check(2 * i - 1); 88     q = check(2 * i); 89     if (!p && !q) { 90       puts("IMPOSSIBLE"); 91       return 0; 92     } 93     else if (p && q) ans[i] = 0; 94     else if (!p) ans[i]= 1; 95     else ans[i] = 2; 96   } 97   for (i = 1; i <= n; ++i) 98     putchar(ch[ans[i]]); 99   puts("");100   return 0;101 }