Samarth and Soham decide to have another shot at the Tour de France. This time there...

Transcribed Image Text:

Samarth and Soham decide to have another shot at the Tour de France. This time there are various checkpoints on the roads in Paris. All the roads are 2-way. After cycling for 10 hours Samarth realizes that they have cycled past the Eiffel Tower too many times. Soham then exclaims, we have been cycling in cycles. Soham now wants to find out how many simple cycles exist, but Samarth wants to find out which checkpoints are part of these cycles. Can you help them figure this out and reach the finish. A simple cycle is a path(at least one road) from a checkpoint to itself visiting other checkpoints atmost once such that no subset of the checkpoints can form a cycle themselves. • Input First line of input consists of two integers N and M which denote the number of checkpoints and the number of roads respectively. The next 2 lines consist of two arrays A and B of size M, which means that there is a road between checkpoint A[i] and B[i] for every 1 ≤ i ≤ M • Output Output the number of simple cycles. In the next line output N integers which are either 1 or 0 such that 1 at ith position indicates that ith checkpoint is a part of one or more cycles, whereas 0 indicates that it is part of no cycles. Constraints 0 1 ≤N ≤ 105 0 0 ≤M ≤ min(N * (N − 1)/2, 105) o 1 ≤ A[i], B[i] ≤ N Vi € [1, N] • Sample Input 1 8 10 1 1 1 7 7 5 8 2 26 2 3 4 1 5 6 4 3 77 • Sample Output 1 3 1 1 1 0 1 1 1 0 • Sample Input 2 77 1 3 3 2 6 5 2 2 2 4 5 5 7 4 • Sample Output 2 1 0 1 1 1 0 0 0 Explanation of Input 1 The map of Paris of Input 1 looks as follows 8 7 3 2 Here there are 3 simple cycles viz. {1,2,3}, {1,2,7}, {5,6,7} Here all checkpoints except 4 and 8 are part of cycles Samarth and Soham decide to have another shot at the Tour de France. This time there are various checkpoints on the roads in Paris. All the roads are 2-way. After cycling for 10 hours Samarth realizes that they have cycled past the Eiffel Tower too many times. Soham then exclaims, we have been cycling in cycles. Soham now wants to find out how many simple cycles exist, but Samarth wants to find out which checkpoints are part of these cycles. Can you help them figure this out and reach the finish. A simple cycle is a path(at least one road) from a checkpoint to itself visiting other checkpoints atmost once such that no subset of the checkpoints can form a cycle themselves. • Input First line of input consists of two integers N and M which denote the number of checkpoints and the number of roads respectively. The next 2 lines consist of two arrays A and B of size M, which means that there is a road between checkpoint A[i] and B[i] for every 1 ≤ i ≤ M • Output Output the number of simple cycles. In the next line output N integers which are either 1 or 0 such that 1 at ith position indicates that ith checkpoint is a part of one or more cycles, whereas 0 indicates that it is part of no cycles. Constraints 0 1 ≤N ≤ 105 0 0 ≤M ≤ min(N * (N − 1)/2, 105) o 1 ≤ A[i], B[i] ≤ N Vi € [1, N] • Sample Input 1 8 10 1 1 1 7 7 5 8 2 26 2 3 4 1 5 6 4 3 77 • Sample Output 1 3 1 1 1 0 1 1 1 0 • Sample Input 2 77 1 3 3 2 6 5 2 2 2 4 5 5 7 4 • Sample Output 2 1 0 1 1 1 0 0 0 Explanation of Input 1 The map of Paris of Input 1 looks as follows 8 7 3 2 Here there are 3 simple cycles viz. {1,2,3}, {1,2,7}, {5,6,7} Here all checkpoints except 4 and 8 are part of cycles

Answer rating: 100% (QA)

Samarth and Soham decide to have another shot at the Tour de France This time there are various chec... View the full answer