fork download
  1. import java.io.*;
  2. import java.math.BigDecimal;
  3. import java.math.BigInteger;
  4. import java.util.*;
  5.  
  6.  
  7.  
  8.  
  9. public class Main {
  10. static class Reader
  11. {
  12. final private int BUFFER_SIZE = 1 << 16;
  13. private DataInputStream din;
  14. private byte[] buffer;
  15. private int bufferPointer, bytesRead;
  16.  
  17. public Reader()
  18. {
  19. din = new DataInputStream(System.in);
  20. buffer = new byte[BUFFER_SIZE];
  21. bufferPointer = bytesRead = 0;
  22. }
  23.  
  24. public Reader(String file_name) throws IOException
  25. {
  26. din = new DataInputStream(new FileInputStream(file_name));
  27. buffer = new byte[BUFFER_SIZE];
  28. bufferPointer = bytesRead = 0;
  29. }
  30.  
  31. public String readLine() throws IOException
  32. {
  33. byte[] buf = new byte[64]; // line length
  34. int cnt = 0, c;
  35. while ((c = read()) != -1)
  36. {
  37. if (c == '\n')
  38. break;
  39. buf[cnt++] = (byte) c;
  40. }
  41. return new String(buf, 0, cnt);
  42. }
  43.  
  44. public int nextInt() throws IOException
  45. {
  46. int ret = 0;
  47. byte c = read();
  48. while (c <= ' ')
  49. c = read();
  50. boolean neg = (c == '-');
  51. if (neg)
  52. c = read();
  53. do
  54. {
  55. ret = ret * 10 + c - '0';
  56. } while ((c = read()) >= '0' && c <= '9');
  57.  
  58. if (neg)
  59. return -ret;
  60. return ret;
  61. }
  62.  
  63. public long nextLong() throws IOException
  64. {
  65. long ret = 0;
  66. byte c = read();
  67. while (c <= ' ')
  68. c = read();
  69. boolean neg = (c == '-');
  70. if (neg)
  71. c = read();
  72. do {
  73. ret = ret * 10 + c - '0';
  74. }
  75. while ((c = read()) >= '0' && c <= '9');
  76. if (neg)
  77. return -ret;
  78. return ret;
  79. }
  80.  
  81. public double nextDouble() throws IOException
  82. {
  83. double ret = 0, div = 1;
  84. byte c = read();
  85. while (c <= ' ')
  86. c = read();
  87. boolean neg = (c == '-');
  88. if (neg)
  89. c = read();
  90.  
  91. do {
  92. ret = ret * 10 + c - '0';
  93. }
  94. while ((c = read()) >= '0' && c <= '9');
  95.  
  96. if (c == '.')
  97. {
  98. while ((c = read()) >= '0' && c <= '9')
  99. {
  100. ret += (c - '0') / (div *= 10);
  101. }
  102. }
  103.  
  104. if (neg)
  105. return -ret;
  106. return ret;
  107. }
  108.  
  109. private void fillBuffer() throws IOException
  110. {
  111. bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
  112. if (bytesRead == -1)
  113. buffer[0] = -1;
  114. }
  115.  
  116. private byte read() throws IOException
  117. {
  118. if (bufferPointer == bytesRead)
  119. fillBuffer();
  120. return buffer[bufferPointer++];
  121. }
  122.  
  123. public void close() throws IOException
  124. {
  125. if (din == null)
  126. return;
  127. din.close();
  128. }
  129. }
  130.  
  131. public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
  132. public static Reader sc = new Reader();
  133.  
  134. static int mod = (int)(1e9+7),MAX=(int)(2e6+10);
  135. static List<Integer>[] edges;
  136.  
  137. public static void main(String[] args) throws IOException{
  138.  
  139. int n = sc.nextInt();
  140. int m = sc.nextInt();
  141.  
  142. edges = new ArrayList[n + 1];
  143. for (int i = 0; i < edges.length; ++i) edges[i] = new ArrayList<>();
  144.  
  145. for (int i = 0; i < m; ++i) {
  146. int u = sc.nextInt();
  147. int v = sc.nextInt();
  148. edges[u].add(v);
  149. edges[v].add(u);
  150. }
  151.  
  152.  
  153. int[] col = new int[n + 1];
  154. Arrays.fill(col, -1);
  155.  
  156. boolean is_bipartite = true;
  157. Queue<Integer> q = new ArrayDeque<>();
  158. for (int st = 1; st <= n && is_bipartite; ++st) {
  159. if (col[st] == -1) {
  160. q.add(st);
  161. col[st] = 0;
  162. while (q.size() > 0) {
  163. int v = q.poll();
  164. for (int node : edges[v]) {
  165. if (col[node] == -1) {
  166. col[node] = col[v] ^ 1;
  167. q.add(node);
  168. } else {
  169. is_bipartite &= col[node] != col[v];
  170. }
  171. }
  172. }
  173. }
  174. }
  175.  
  176. if (is_bipartite) {
  177. for (int i = 1; i <= n; ++i) out.print((col[i] + 1) + " ");
  178. } else out.println("IMPOSSIBLE");
  179. out.close();
  180. }
  181.  
  182. }
Success #stdin #stdout 0.09s 34100KB
stdin
5 3
1 2
1 3
4 5
stdout
1 2 2 1 2