Guest User

buildteam

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