ZYB likes to readdetective novels anddetective cartoons. One day he is immersed in such story: As a spy of country B, you have been lurking in country A for many years. There are nnn troops
ZYB likes to read detective novels and detective cartoons. One day he is immersed in such story: As a spy of country B, you have been lurking in country A for many years. There are nnn troops and mmm legions in country A, and each troop belongs to only one legion. Your task is to investigate which legion each troop belongs to. One day, you intercept a top secret message--a paper which records all the pairwise relationship between troops. You can learn from the paper that whether troop i{i}i and troop j{j}j belongs to the same legion for each (i,j){(i,j)}(i,j). However, each piece of data has a independent probability of 1Sfrac{1}{S}S1 being reversed. Formally, the troop is numbered from 0{0}0 to n−1{n-1}n−1, and the region is numbered from 0{0}0 to m−1{m-1}m−1. You are given n(n−1)2frac{n(n-1)}{2}2n(n−1) boolean numbers, indicating whether i{i}i and j{j}j belong to the same region (1 for yes and 0 for no). However, every number will be reversed(i.e., 0 to 1 and 1 to 0) in a probablity of 1Sfrac{1}{S}S1. You can assume that the data is generated like this: be[i] means the region that troop i{i}i belongs to. rand() can be considered as a uniform random function. i.e., select a integer from interval [0,lcm(m,S)−1][0, mathrm{lcm}(m, S)-1][0,lcm(m,S)−1] with equal probability. Note that you have already known n{n}n and S{S}S, but you don't know the exact value of mmm. Please help country B construct the original data.
