Guest User

Untitled

a guest
Jun 25th, 2020
74
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4.  
  5. public class buildteam{
  6. static long mod = (long)(pow(10, 9) + 7);
  7. static int n;
  8. static int[] team;
  9. static List<List<Integer>> adj;
  10. static void fill(int i) {
  11. Queue<Integer> q = new ArrayDeque<Integer>();;
  12. q.add(i);
  13. team[i] = 1;
  14. while (!q.isEmpty()) {
  15. int head = q.poll();
  16. for (int x: adj.get(head)) {
  17. if (team[x] == 0) {
  18. team[x] = 3-team[head];
  19. q.add(x);
  20. }
  21. else if (team[x] == team[head]) {
  22. out.println("IMPOSSIBLE");
  23. out.close();
  24. System.exit(0);
  25. }
  26. }
  27. }
  28. }
  29. public static void main(String[] args) {
  30. MyScanner sc = new MyScanner();
  31. out = new PrintWriter(new BufferedOutputStream(System.out));
  32. n = sc.nextInt();
  33. int m = sc.nextInt();
  34. team = new int[n];
  35. adj = new ArrayList<List<Integer>>();
  36. for (int i = 0; i < n; i++) {
  37. adj.add(new ArrayList<Integer>());
  38. }
  39. for (int i = 0; i < m; i++) {
  40. int a = sc.nextInt()-1;
  41. int b = sc.nextInt()-1;
  42. adj.get(a).add(b);
  43. adj.get(b).add(a);
  44. }
  45. for (int i = 0; i < n; i++) {
  46. if (team[i] == 0) {
  47. fill(i);
  48. }
  49. }
  50.  
  51. for (int x: team) out.print(x + " ");
  52. out.println();
  53.  
  54.  
  55.  
  56.  
  57.  
  58. out.close();
  59. }
  60.  
  61. static long pow(long a, long N) {
  62. if (N == 0) return 1;
  63. else if (N == 1) return a;
  64. else {
  65. long R = pow(a,N/2);
  66. if (N % 2 == 0) {
  67. return R*R;
  68. }
  69. else {
  70. return R*R*a;
  71. }
  72. }
  73. }
  74.  
  75.  
  76. static long powMod(long a, long N) {
  77. if (N == 0) return 1;
  78. else if (N == 1) return a % mod;
  79. else {
  80. long R = powMod(a,N/2) % mod;
  81. // out.println(R);
  82. R = R * R % mod;
  83. if (N % 2 == 1) {
  84. R = R* a % mod;
  85. }
  86. return R % mod;
  87. }
  88. }
  89.  
  90.  
  91.  
  92.  
  93. //-----------PrintWriter for faster output---------------------------------
  94. public static PrintWriter out;
  95.  
  96. //-----------MyScanner class for faster input----------
  97. public static class MyScanner {
  98. BufferedReader br;
  99. StringTokenizer st;
  100.  
  101. public MyScanner() {
  102. br = new BufferedReader(new InputStreamReader(System.in));
  103. }
  104.  
  105. String next() {
  106. while (st == null || !st.hasMoreElements()) {
  107. try {
  108. st = new StringTokenizer(br.readLine());
  109. } catch (IOException e) {
  110. e.printStackTrace();
  111. }
  112. }
  113. return st.nextToken();
  114. }
  115.  
  116. int nextInt() {
  117. return Integer.parseInt(next());
  118. }
  119.  
  120. long nextLong() {
  121. return Long.parseLong(next());
  122. }
  123.  
  124. double nextDouble() {
  125. return Double.parseDouble(next());
  126. }
  127.  
  128. String nextLine(){
  129. String str = "";
  130. try {
  131. str = br.readLine();
  132. } catch (IOException e) {
  133. e.printStackTrace();
  134. }
  135. return str;
  136. }
  137.  
  138. }
  139. //--------------------------------------------------------
  140. }
RAW Paste Data