#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <tuple>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;
class TwistyPassages { public:
vector<int> similarRooms(vector<string> maze)
{
map<int,int> e2o;
Graph org = parse_graph(maze); // original graph
Graph exg = construct_extended_graph(org, &e2o); // extended graph
Groups groups = grouping(exg); // grouping
// similar[ov] = set of nodes indistinguishable from ov (in original graph)
vector<set<int>> similar(maze.size());
for(auto& e_grp: groups) {
set<int> o_grp;
for(int ev: e_grp)
o_grp.insert(e2o[ev]);
for(int ov: o_grp)
similar[ov].insert(o_grp.begin(), o_grp.end());
}
// similar[ov]-1 is the answer.
vector<int> answer(maze.size());
transform(similar.begin(), similar.end(), answer.begin(),
[](const set<int>& g){return g.size()-1;});
return answer;
}
typedef vector<vector<int>> Graph;
Graph parse_graph(const vector<string>& maze)
{
Graph g;
for(auto& m: maze) {
stringstream ss(m);
g.emplace_back(istream_iterator<int>(ss), istream_iterator<int>());
}
return g;
}
Graph construct_extended_graph(const Graph& org, map<int,int>* e2o)
{
map<pair<int,int>, int> o2e;
for(int v=0,id=0; v<org.size(); ++v) {
// special handling for outdeg = 0 node
if(org[v].size() == 0) {
(*e2o)[id] = v;
o2e[make_pair(v,0)] = id++;
}
for(int vi=0; vi<org[v].size(); ++vi) {
(*e2o)[id] = v;
o2e[make_pair(v,vi)] = id++;
}
}
Graph exg(o2e.size());
map<pair<int,int>, int> nodeid;
for(int v=0; v<org.size(); ++v)
for(int vi=0; vi<org[v].size(); ++vi) {
// (v,vi) : came to the room v from the vi-th road.
for(int k=0; k<org[v].size(); ++k) {
// Go k-th road clockwise from i-th. Reaches (u,ui).
int u = org[v][(vi+k) % org[v].size()];
int ui = find(org[u].begin(), org[u].end(), v) - org[u].begin();
// (v,vi)--k-->(u,ui)
exg[o2e[make_pair(v,vi)]].push_back(o2e[make_pair(u,ui)]);
}
}
return exg;
}
typedef set<set<int>> Groups;
Groups grouping(const Graph& G)
{
// "reverse_edge[u][e] has v" := v--e-->u
const int MaxEdgeNum = G.size();
vector<vector<vector<int>>> reverse_edge(G.size(), vector<vector<int>>(MaxEdgeNum));
for(int v=0; v<G.size(); ++v)
for(int e=0; e<G[v].size(); ++e)
reverse_edge[G[v][e]][e].push_back(v);
vector<int> group_id(G.size());
map<int, set<int>> groups;
int fresh_group_id = 0;
for(int v=0; v<G.size(); ++v) {
groups[G[v].size()].insert(v);
group_id[v] = G[v].size();
fresh_group_id = max(fresh_group_id, group_id[v]+1);
}
queue<set<int>> partitioner;
for(auto& kv: groups)
partitioner.push(kv.second);
while(!partitioner.empty())
{
set<int> P = partitioner.front();
partitioner.pop();
for(int e=0; e<MaxEdgeNum; ++e)
{
map<int, set<int>> g2u;
for(int v: P)
for(int u: reverse_edge[v][e])
g2u[group_id[u]].insert(u);
for(auto& kv: g2u) {
int gid = kv.first;
set<int>& enterP = kv.second;
if(groups[gid].size() != enterP.size()) {
for(int u: enterP) {
group_id[u] = fresh_group_id;
groups[gid].erase(u);
}
groups[fresh_group_id++] = enterP;
partitioner.push(enterP.size() < groups[gid].size() ? enterP : groups[gid]);
}
}
}
}
Groups result;
for(auto& kv: groups)
result.insert(kv.second);
return result;
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
{ ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const vector <int>& Expected, const vector <int>& Received) {
bool ok = (Expected == Received);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(_, TwistyPassages().similarRooms(maze));}
int main(){
CASE(0)
string maze_[] = {"1 2 3", "0", "0", "0"};
vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_));
int __[] = {0, 2, 2, 2 };
vector <int> _(__, __+sizeof(__)/sizeof(*__));
END
CASE(1)
string maze_[] = {"1 2 3", "0", "0", "0 4", "3"};
vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_));
int __[] = {0, 0, 0, 0, 0 };
vector <int> _(__, __+sizeof(__)/sizeof(*__));
END
CASE(2)
string maze_[] = {"1 2 3", "0", "0", "0 4", "3",
"6 7 8", "5", "5", "5 9", "8"};
vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_));
int __[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
vector <int> _(__, __+sizeof(__)/sizeof(*__));
END
CASE(3)
string maze_[] = {"1 2 3 4", "0", "0 5", "0", "6 0", "2", "4",
"8 10 9 11", "7", "7 12", "7", "13 7", "9", "11"};
vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_));
int __[] = {0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0 };
vector <int> _(__, __+sizeof(__)/sizeof(*__));
END
CASE(4)
string maze_[] = {"1 2", "2 0", "0 1", "4 6", "5 3", "6 4", "3 5"};
vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_));
int __[] = {6, 6, 6, 6, 6, 6, 6 };
vector <int> _(__, __+sizeof(__)/sizeof(*__));
END
CASE(5)
string maze_[] = {"1 2 3", "4 5 0", "6 7 0", "8 9 0", "10 11 1", "12 13 1",
"14 15 2", "16 17 2", "18 19 3", "20 21 3", "22 23 4",
"24 25 4", "26 27 5", "28 29 5", "30 31 6", "32 33 6",
"34 35 7", "36 37 7", "38 39 8", "40 41 8", "42 43 9",
"44 45 9", "10", "10", "11", "11", "12", "12", "13", "13",
"14", "14", "15", "15", "16", "16", "17", "17", "18", "18",
"19", "19", "20", "20", "21", "21"};
vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_));
int __[] = {0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 };
vector <int> _(__, __+sizeof(__)/sizeof(*__));
END
CASE(6)
string maze_[] = {"38 7 9 8 43 48 30 41 5 22 26 35 33 4", "14 39 25 35 30 45 18 12 10 8 21 46 22 37 20", "15 37 26 44 19 17 39 16 7 18 45 36 20 42 24", "21 43 26 8 28 10 4 48 25 46 49 31 37 27 15", "8 31 30 3 0 36 41 5 34 25 44 32 9 14 22", "46 33 38 4 47 34 17 6 45 10 41 48 31 43 0", "5 40 17 19 22 43 18 47 31 9 7 15 29 28 23", "19 38 21 11 34 31 9 0 48 30 44 2 26 16 6", "48 12 3 49 0 41 1 28 35 40 36 4 29 33 43", "18 36 6 47 26 37 27 22 0 46 23 41 4 24 7", "42 13 35 28 31 12 11 3 1 20 16 45 19 40 5", "14 15 45 46 13 7 27 39 25 38 44 17 16 10 43", "48 8 15 42 47 10 29 45 39 1 19 25 44 32 26", "47 24 11 36 41 42 16 38 37 20 32 31 45 29 10", "31 48 49 25 11 38 18 23 43 4 22 41 24 1 27", "32 34 23 11 6 43 2 22 48 45 17 41 12 16 3", "7 46 18 28 20 19 43 31 27 2 15 13 39 10 11", "19 26 28 2 30 23 15 5 24 47 25 18 6 42 11", "26 6 24 46 17 42 45 14 16 9 22 27 1 33 2", "30 6 17 37 39 33 49 2 21 46 16 27 7 10 12", "13 32 41 1 39 16 42 27 2 33 40 24 45 48 10", "36 37 41 1 30 7 23 35 40 44 26 47 39 3 19", "14 6 23 40 0 43 9 29 1 18 31 15 28 34 4", "30 14 6 28 34 22 48 9 40 21 42 17 15 37 32", "48 40 44 26 9 20 13 43 17 2 18 29 14 42 46", "32 12 43 1 17 39 29 14 3 36 11 40 4 49 33", "0 7 39 3 12 49 38 36 21 29 18 17 9 2 24", "29 28 38 16 18 46 9 3 35 36 40 20 14 11 19", "33 39 35 38 3 6 22 10 23 17 27 46 16 8 42", "13 26 25 37 33 44 12 48 6 41 46 24 8 22 27", "34 41 38 21 0 19 23 4 7 49 1 44 17 40 35", "3 14 32 4 5 37 7 6 13 10 22 16 44 47 49", "15 4 13 31 38 23 42 20 12 46 35 25 43 34 37", "39 44 19 0 18 28 20 37 29 48 8 45 25 5 34", "36 44 47 7 15 4 33 30 42 32 22 40 5 23 41", "40 27 42 8 45 32 10 0 28 1 49 46 30 47 21", "4 2 21 47 8 38 27 45 39 13 49 26 9 25 34", "42 21 31 29 13 47 32 3 9 33 2 23 45 1 19", "0 43 7 28 44 13 27 32 49 14 36 11 5 30 26", "16 36 21 20 12 48 26 41 2 11 28 33 1 19 25", "8 22 10 6 35 20 25 23 41 27 30 24 44 34 21", "13 29 39 15 0 30 40 20 4 5 34 14 8 9 21", "28 10 32 17 34 37 13 2 18 20 12 24 35 49 23", "5 47 25 24 11 8 14 38 16 6 32 15 22 3 0", "40 38 30 21 31 46 34 29 11 33 4 12 24 2 7", "35 49 36 10 12 11 37 18 33 2 20 1 13 15 5", "3 28 35 1 19 9 18 27 32 44 24 11 29 16 5", "9 43 6 31 12 13 35 21 36 5 49 34 48 17 37", "24 33 5 8 15 12 47 29 0 7 23 20 14 39 3", "19 3 14 8 38 47 30 36 35 25 31 26 42 45"};
;
vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_));
int __[] = {0};
vector <int> _(__, __+sizeof(__)/sizeof(*__));
END
/*
CASE(7)
string maze_[] = ;
vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_));
int __[] = ;
vector <int> _(__, __+sizeof(__)/sizeof(*__));
END
*/
}
// END CUT HERE