#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 <cstring>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;
typedef int vert;
typedef vert edge;
typedef vector<edge> edges;
typedef vector<edges> graph;
bool augment( graph& G, int v, vector<vert>& matchTo, bool visited[] )
{
for(int i=0; i<G[v].size(); ++i) {
vert u = G[v][i];
if( visited[u] ) continue;
visited[u] = true;
if( matchTo[u]<0 || augment(G, matchTo[u], matchTo, visited) )
{ matchTo[v]=u, matchTo[u]=v; return true; }
}
return false;
}
template<int NV>
int biMatch( graph& G, int L ) // [0,L):left, [L,?):right
{
vector<vert> matchTo(G.size(), -1);
int ans = 0;
for(vert v=0; v<L; ++v) {
bool visited[NV] = {};
if( augment(G, v, matchTo, visited) )
++ans;
}
return ans;
}
int bitcnt(LL x)
{
int c = 0;
for(; x; x>>=1)
c += x&1;
return c;
}
class MallSecurity { public:
pair<graph, int> generateBipartiteGraph(
const vector<int>& As, const vector<int>& Bs, const vector<int>& Cs, const vector<int>& Ds,
const vector<int>& Ks, int msf, int mask )
{
// construct a bipartite graph representation, in which
// - "even"-floor stations go to the left
// - "odd"-floor stations go to the right
// here floor number is normalized by rotating the msf-th floor to zero
#define LR(f) (((f)>msf ? (f)-msf : Ks.size()-msf+(f))%2)
// assign interger-ID for each "choosable" station, i.e.,
// a station which is not at msf and is not connected to a 'mask'ed station on msf
map<pair<int,int>,int> ID;
int nextID[2] = {0,0}; // use different sets of IDs for even/odd floors
{
for(int f=0; f<Ks.size(); ++f) if( f != msf )
for(int i=0; i<Ks[f]; ++i)
{
bool can_use = true;
for(int j=0; j<As.size(); ++j)
if( Cs[j]==f && As[j]==i && Ds[j]==msf && (mask & 1<<Bs[j])
|| Ds[j]==f && Bs[j]==i && Cs[j]==msf && (mask & 1<<As[j]) )
can_use = false;
if( can_use )
ID[make_pair(f,i)] = nextID[LR(f)]++;
}
}
// then create the graph
graph G( nextID[0] + nextID[1] );
for(int j=0; j<As.size(); ++j)
{
pair<int,int> p(Cs[j], As[j]);
pair<int,int> q(Ds[j], Bs[j]);
if( ID.count(p) && ID.count(q) )
{
int pid = ID[p] + (LR(Cs[j]) ? nextID[0] : 0);
int qid = ID[q] + (LR(Ds[j]) ? nextID[0] : 0);
G[pid].push_back(qid);
G[qid].push_back(pid);
}
}
return make_pair(G, nextID[0]);
}
int maxGuards(int N, vector <string> escDescription)
{
// parse the input
vector<int> As, Bs, Cs, Ds, Ks(N);
{
stringstream sin;
copy( escDescription.begin(), escDescription.end(), ostream_iterator<string>(sin,"") );
for(int A,B,C; sin>>A>>B>>C; )
{
{char comma; sin>>comma;}
--A, --B, --C; int D=(C+1)%N; // to 0-orign
As.push_back(A);
Bs.push_back(B);
Cs.push_back(C);
Ds.push_back(D);
Ks[C] = max(Ks[C], A+1);
Ks[D] = max(Ks[D], B+1);
}
}
// the most simple floor, where the number Ks[msf] of stations is the least
int msf = min_element(Ks.begin(), Ks.end()) - Ks.begin();
// try all possibilities at the msf-th floor
size_t answer = 0;
for(int mask=0; mask<(1<<Ks[msf]); ++mask)
{
// then the rest of the part becomes a bipartite graph
pair<graph, int> G = generateBipartiteGraph(As,Bs,Cs,Ds,Ks,msf,mask);
// |MaxIndenepdentSet| == |V|-|MinCover| =(for bipartite graphs)= |V|-|MaxMatch|
answer = max(answer, G.first.size() - biMatch<100>(G.first,G.second) + bitcnt(mask));
}
return answer;
}
};
// 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 int& Expected, const 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(_, MallSecurity().maxGuards(N, escDescription));}
int main(){
CASE(0)
int N = 10;
string escDescription_[] = {"1 1 1,1 1 2,1 1 3,1 1 4,1 1 5,1 1 6,1 1 7,1 1 8,1 ",
"1 9,1 1 10"};
vector <string> escDescription(escDescription_, escDescription_+sizeof(escDescription_)/sizeof(*escDescription_));
int _ = 5;
END
CASE(1)
int N = 11;
string escDescription_[] = {"1 1 1,1 1 2,1 1 3,1 1 4,1 1 5,1 1 6,1 1 7,1 1 8,1 ",
"1 9,1 1 10"};
vector <string> escDescription(escDescription_, escDescription_+sizeof(escDescription_)/sizeof(*escDescription_));
int _ = 6;
END
CASE(2)
int N = 10;
string escDescription_[] = {"1 1 7,1 2 9,2 1",
" 8,1 2 6,1 1 8,1 2 3,1 2 2,2 ",
"2 4,1 1 1,2 1 2,3 2 3,1 1 5,2 1 1,4 ",
"1 7,1 1 10,3 2 5,1 2 5,3 3 1,",
"3 2 8,3 1 2,1 1 3,4 4 2,2",
" 4 6,4 2 5,2 3 3,6 4 1,5 2 8,1 3 6,1 3 7,",
"4 3 8,1 3 8,5 2 3,4 2 8,2 6 7,1 3 9,",
"1 1 4,6 1 1,2 3 1,5 1 5,6 1 8,5 ",
"2 2,3 2 10,3 3 9,1 5 2,4 1 1,1 5 10"};
vector <string> escDescription(escDescription_, escDescription_+sizeof(escDescription_)/sizeof(*escDescription_));
int _ = 25;
END
CASE(3)
int N = 13;
string escDescription_[] = {"5 1 11,2 3 9,3 7 10,5 2 11,5 5 8,7 5 6,5 2 13,4 2 ", "8,3 7 12,7 3 9,2 7 12,8 5 4,4 6 6,7 3 11,1 5 7,4 4", " 10,3 1 9,7 2 5,4 6 12,5 5 5,6 6 5,1 5 12,6 4 3,2 ", "5 1,2 5 5,5 4 3,5 6 8,3 5 11,6 2 7,8 3 7,6 8 2,5 3", " 12,6 1 3,6 2 8,6 2 6,5 5 6,3 2 2,4 3 11,1 8 2,3 4", " 5,1 6 8,5 7 6,3 2 7,4 1 9,4 7 8,4 3 7,4 5 4,2 1 7", ",5 4 2,6 5 4,6 8 13,2 6 3,6 3 6,3 4 7,4 5 8,1 3 11", ",6 6 1,5 1 8,3 5 7,7 3 4,3 4 13,5 4 6,7 4 1,3 1 13", ",1 5 6,7 7 12,4 7 3,7 4 4,1 6 10,3 4 6,7 4 10,5 3 ", "13,1 1 4,8 7 7,2 7 13,5 6 11,1 4 9,4 4 13,2 6 8,7 ", "5 10,1 2 7,1 7 8,8 8 3,2 4 1,7 6 12,2 5 12,2 2 3,1", " 2 2,1 4 7,4 1 11,6 2 4,4 6 4,6 3 8,5 6 7,4 2 4,2 ", "7 6,7 2 1,3 4 4,4 4 3,1 2 3,1 1 10,2 3 8,6 6 11,5 ", "5 13,7 7 4,5 3 11,6 6 8,6 4 12,6 1 7,3 8 9,2 1 1,5", " 5 10,8 1 7,7 2 6,1 7 4,5 1 12,2 5 7,6 7 7,3 6 3,8", " 1 1,3 8 2,3 6 6,3 6 4,6 3 2,4 5 5,2 6 4,3 2 6,7 6", " 5,1 8 6,5 5 4,2 7 10", ",1 7 9,1 1 3,4 4 4,4 3 5,4 2 10,5 7 3,5 3 5,3 6 9,", "2 5 11,3 2 3,4 1 1,2 5 10,5 1 4,6 5 5,1 7 5,7 5 5,", "8 5 12,7 8 13,1 2 10,3 7 6,4 7 13,4 3 13,6 4 11,6 ", "7 4,2 6 7,2 7 3,7 8 8,6 1 12,6 7 8,3 1 10,8 6 1,1 ", "7 10,1 3 9,7 7 11,5 6 4,7 7 1,4 2 1,8 2 3,7 8 2,1 ", "4 13,2 3 13,3 2 11,6 7 12,4 8 2,5 6 1,6 3 12,3 5 3", ",1 5 10,1 4 5,4 6 10,1 6 6,6 3 5,4 3 12,6 2 11,3 8", " 3,7 5 3,6 7 10,3 2 13,7 4 3,1 7 12,2 7 4,4 7 1,8 ", "5 10,6 6 4,6 7 2,4 7 7,1 3 1,1 4 12,6 5 7,5 1 13,5", " 8 13,2 1 10,5 2 7,8 3 10,5 1 5,1 4 6,1 1 6,5 2 2,", "2 3 11,3 2 10,2 1 13,8 2 9,3 5 2,1 7 2,3 3 5,5 2 5", ",8 4 12,7 3 2,2 5 3,3 7 1,6 7 6,8 5 9,4 5 7,2 8 3,", "2 4 6,7 1 10,5 8 11,4 7 6,7 6 4,3 6 11,5 3 1,7 7 8", ",1 6 9,7 6 7,1 2 1,2 2 12,3 5 9,4 4 1,6 4 5,5 8 3,", "2 1 2,6 6 10,1 5 9,8 1 3,5 1 10,4 7 2,8 4 9,2 2 7,", "2 3 4,6 1 4,1 4 11,7 1 1,3 7 7,5 4 13,1 6 1,4 7 12"};
vector <string> escDescription(escDescription_, escDescription_+sizeof(escDescription_)/sizeof(*escDescription_));
int _ = 50;
END
/*
CASE(4)
int N = ;
string escDescription_[] = ;
vector <string> escDescription(escDescription_, escDescription_+sizeof(escDescription_)/sizeof(*escDescription_));
int _ = ;
END
*/
}
// END CUT HERE