fork download
  1. /*
  2. 【感想・工夫した点など】
  3. 線対称となる先の位置を数値ではなく文字のまま求めるようにしてみたところ、
  4. よく考えたらJavaには「y/.../.../」みたいな一括文字置換がないので
  5. 全く意味がなかったんですが、いまさら換字表を配列で書きなおすのも面倒なので
  6. そのまま押し切りましたw
  7.  
  8. メモリとか速度とかは、自分のマシンで十二分に動作するので気にしません(・∀・)
  9. */
  10. import java.io.BufferedReader;
  11. import java.io.FileInputStream;
  12. import java.io.InputStreamReader;
  13. import java.util.Arrays;
  14.  
  15.  
  16. public class Main {
  17.  
  18. // 頂点群のうち、ある頂点を通る直線で線対称にする換字列を返す
  19. public static String symmOnVertex(char vertex, String vertexen) {
  20. String rev = new StringBuilder(vertexen).reverse().toString();
  21. String sub = (rev+rev).substring(rev.indexOf(vertex), rev.indexOf(vertex)+vertexen.length());
  22. if (vertex != 'A') {
  23. sub = sub.substring(vertexen.length()-vertex+'A') + sub.substring(0, vertexen.length()-vertex+'A');
  24. }
  25. return sub;
  26. }
  27.  
  28. // 頂点群のある辺の中点を通る直線で線対称にする換字列を返す
  29. public static String symmOnEdge(char vertex, String vertexen) {
  30. // 倍の頂点数に変換
  31. StringBuilder sb = new StringBuilder();
  32. for (int i = 0 ; i < 2*vertexen.length() ; i++) sb.append((char)('A'+i));
  33. String vertexen2 = sb.toString();
  34. char vertex2 = (char)((vertex-'A')*2+1+'A');
  35. // 倍の頂点数で頂点を通る直線で線対称を取る
  36. String table2 = symmOnVertex(vertex2, vertexen2);
  37. // 元の頂点数に戻す
  38. sb = new StringBuilder();
  39. for (int i = 0 ; i < 2*vertexen.length() ; i+=2) sb.append((char)('A'+(table2.charAt(i)-'A')/2));
  40. return sb.toString();
  41. }
  42.  
  43. public static String sortEdgeName(String edge) {
  44. String[] edges = new String[] {edge, new StringBuilder().append(edge.charAt(1)).append(edge.charAt(0)).toString()};
  45. Arrays.sort(edges);
  46. return new String(edges[0]);
  47. }
  48.  
  49. public static String[] oprateSymm(int type, char vertex, int num, String[] edges) {
  50. String vertexen = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".substring(0, num);
  51. String table = null;
  52. if (type == 0) // 頂点を通る直線による線対称操作
  53. table = symmOnVertex(vertex, vertexen);
  54. else // 辺中点を通る直線による線対称操作
  55. table = symmOnEdge(vertex, vertexen);
  56. String[] ret = new String[edges.length];
  57. for (int i = 0 ; i < edges.length ; i++) {
  58. ret[i] = sortEdgeName(String.format("%c%c", table.charAt(edges[i].charAt(0)-'A'), table.charAt(edges[i].charAt(1)-'A')));
  59. }
  60. Arrays.sort(ret);
  61. return ret;
  62. }
  63.  
  64. public static void main(String[] args) throws Exception {
  65. //BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("C:\\data.txt")));
  66.  
  67. String line = null;
  68. while ((line = br.readLine()) != null) {
  69. String[] terms = line.split("\t");
  70.  
  71. int num_vertexen = Integer.parseInt(terms[1]); // 頂点数
  72. int num_symm_pred = Integer.parseInt(terms[3]); // 予想される線対称数
  73.  
  74. // 辺群の正規化
  75. String[] edges_org = terms[2].split(",");
  76. String[] edges_norm = new String[edges_org.length];
  77. for (int i = 0 ; i < edges_org.length ; i++) edges_norm[i] = sortEdgeName(edges_org[i]);
  78. Arrays.sort(edges_norm);
  79.  
  80. // 頂点数の偶奇で対象操作を分ける
  81. int num_symm_obs = 0; // 確認された線対称数
  82. if (num_vertexen%2 == 0) { // 頂点数が偶数
  83. // まず、半数の頂点を通る直線で線対称操作をおこなう
  84. for (int i = 0 ; i < num_vertexen/2 ; i++) {
  85. String[] symmed = oprateSymm(0, (char)('A'+i), num_vertexen, edges_norm);
  86. if (Arrays.deepEquals(edges_norm, symmed)) num_symm_obs++;
  87. }
  88. // つぎに、半数の辺中点を通る直線で線対称操作をおこなう
  89. for (int i = 0 ; i < num_vertexen/2 ; i++) {
  90. String[] symmed = oprateSymm(1, (char)('A'+i), num_vertexen, edges_norm);
  91. if (Arrays.deepEquals(edges_norm, symmed)) num_symm_obs++;
  92. }
  93. } else { // 頂点数が奇数
  94. // 全頂点を通る直線で線対称操作をおこなう
  95. for (int i = 0 ; i < num_vertexen ; i++) {
  96. String[] symmed = oprateSymm(0, (char)('A'+i), num_vertexen, edges_norm);
  97. if (Arrays.deepEquals(edges_norm, symmed)) num_symm_obs++;
  98. }
  99. }
  100.  
  101. // 判定
  102. if (num_symm_obs != num_symm_pred)
  103. System.out.println("× ("+num_symm_obs+") "+line);
  104. }
  105.  
  106. }
  107. }
Success #stdin #stdout 0.35s 321856KB
stdin
T0	6	BE,EC,CF,FB	2
T1	12	HB,GD,FC,JA,LI	2
T2	14	LM,EB,CM,BA,HJ,GD,KE,GL,NF,MI,DK,LH,HA,KF,KH,DJ,KB,JL,AE,IG,CD,KJ,GK	0
T3	10	HF,DB,CH,AI,IJ,DI,HD,GJ,AF,BH,BE,DF,HJ,CJ,DJ,BI,CB,AC	1
T4	6	ED,BF,AB,BD	0
T5	6	DB,EC,FE,FD,EA,DC,FB,BA,AC	3
T6	8	FH,FA,FB,DC,AG,AC,AE,GD,CB,BD,AH,AD,EH,CF,FD,EF,CH,BA,EC,HG,EG,CG,HD,BG,BE,ED	0
T7	10	FH,HI,DF,JH,IC,IB,HC,EJ,AC,GI,EF,BC,HB,IF,GF,BD,HD,GA,EA,GC,BG,JD,ID,IA,CD,BJ,FC	0
T8	9	BI,HB,EH,GA,GI,DE,DA	1
T9	12	GF,CD,HC,EJ,AL,FB,KG,CJ,ID,KF,EI,HD,LG,LH,BG,IJ,AF,IB,HA,BJ,KC,EL,EA,KD	4
T10	10	FI,JD,AE,AF,GF,JC,IC,GB,GD,EI,HD,FE,GH,DI,HB	1
T11	9	GH,CD,IH	1
T12	8	CB,HG,CD,BA,HA,FG,DE,FE	8
T13	12	EG,IG,CA,DF,HE,LI,GB,BL,CJ,AD,LJ,JH,KI,CE,FK,AK,DB,FH	3
T14	16	LN,PC,FC,PN,OL,BP,BD,FH,JL,JH,FD,GJ,BO,NK,KH,DG	4
T15	12	AG,HC,BJ,EL,DB,GJ,JF,DF,AJ	1
T16	12	FH,DB,LJ	3
T17	9	DE,FI,GB,AE,HG,CI,DH,AH,ID,EI,DF,GC,AB,CE,HF,AC,IG,BI,FB	1
T18	8	GD,CH,AB,EF	2
T19	14	DM,MI,LE,DL,AG,FA,FJ,NG	1
T20	8	BE,FC,BH,GB,GA,HE,BC,HF,CE,DG,FG,AD,HG,FD,EG,BA,CD,CH,AF,HA,EF,DB,AC,DE	8
T21	8	CG,DB,HE,BE,FC,AF,CH,DA	1
T22	12	JL,CA,FD,IG	4
T23	9	BI,HB,BE,GI,FH,AG,DF,IA,EH,FG,BD,AD,CB,EG,GD,FE,IH,EC,AC,DC,HA	3
T24	8	AB,HC,EH,CD,FA,EB,FG,CA,DE,BG,GD,DF,EG,GH,AD,AH,BC,CF,FE,HB	2
T25	15	OH,NH,OB,LJ,HG,FA,GC,LI,JI	0
T26	15	LC,IN,IA,AJ,DL,KD,BJ,DN,BI,AB,KL,DI,CK	1
T27	15	MD,NH,CI,JA,GE,DB,KE,BO,FO,IG,LN,JL	3
T28	12	JA,AH,KC,DK,DI,EG,DE,BL,IL,AB,KH,HJ,IH,LC,EB,DH,CB,BI	0
T29	24	FP,DR,DN,BP	2
T30	15	CN,LO,AB,BC,GD,GM,FL,AE	1
T31	15	BM,BF,HL,KG,AL,CG	3
T32	20	FC,KM,GJ,FH,QT,MP,TB,OQ,JL,AR,RP,OL,HK,BE,EG,CA	4
T33	16	AL,HK,CF,BM,ID,IF,HE,JE,CP,KN,NA,MP	2
T34	18	FK,RN,BM,RM,BF,NJ,IQ,JP,GL,NQ,PR,CK,LQ,GQ,RK,OF,DR,FG,EO,BA,GH,IE,DO,KA,JH,IF,OQ,NE,CL,GN	0
T35	10	HI,EI,BD,EH,EB,DE,JI,AH,FH,GH,GF,FD,AD,JB,JH,AB,AG,IG	1
T36	20	TP,FJ,AE,KO	4
T37	14	KJ,DB,CK,HC,AM,GL,BH,CN,MN,EN,HA,MF,DN,KE,NL,ID,EG,KL,IF,AL,ML,AC,BJ,DJ,IM,KF	0
T38	14	NF,KH,EM,GM,NC,FC,EB,LI,KN,BH,AD,NH,CI,CK,KE,GJ,FL,JM,JD,LA,HE,LD,FI,AI,BJ,GD,GA,BM	14
T39	14	KI,LI,LA,LN,BM,DA,GJ,IF,KM,MJ,LJ,HJ,DG	1
T40	20	BG,OT,FB,TP,FJ,GJ,LO,EJ,LQ,QT,LP,BE	2
T41	26	GX,GT,CE,MH,MI,SH,IK,UD,MB,WY,OZ,OS,IT,TO,UH,SQ	1
T42	24	WN,OF,EW,JQ,IX,QH,FM,RX	1
T43	18	NM,CB,QR,CD,EF,NO,GF,HG,ML,IJ,PO,ED,QP,LK,RA,AB,HI,JK	18
T44	14	BH,AJ,GK,KD,DC,HI,CK,DF,BA,AL,JI,EI,HN,BF,GI,GN,EM	0
T45	18	IB,FD,MF,OP,DH,NA,BF,RG,IC,PD,EF,OQ,LD,FL,GE,PL,QR,JI,QJ,RI,JR,FG,GA,MO,HB	0
T46	15	AO,CL,GK,MI,AE,MO,NM,FD,HC,NJ,BM,KH,CN,NL,GI,CE,OI,DA,ID,LK,FH	1
T47	21	CB,ST,QJ,UD,UJ,RP,FD,GJ,LE,GS,LA,HQ,HA,MC,EN,UF,LO,PA,UQ,NU,RA,CO,IS,AE	1
T48	16	OD,EH,HC,GJ,OB,PK,MP,GL	2
T49	25	GD,MS,HK,BU	1
100	6	AE,EF,DC,ED,BA,DF	0
101	9	GI,IC,FI,CE,GD,BG,AH,FD,BF,GF,DA	1
102	8	AD,HA,FD,BA,FC,CD,EA,ED,GE,HD,EH,EB,DG,EF,GB,FA,GF,HB,CH,CA,BC,CE	0
103	16	EH,MP,BO,GD,JM,LO,JG,EB	2
104	9	EG,CH,CG,FB,AE,EC,FD,BG,GI,HA,IE,FA,CA,ID,DH,BI,HF,BD	9
105	5	BE,ED,BC,AD,CA,AE,AB,BD,DC,CE	5
106	8	ED,BH,FE,EB,AF,HC,GD,BA,AH,CE,HG,FD,GA,CD	2
107	15	JD,HN,MG,AG,MD,JA,KB,HB,EN,KE	5
108	14	EL,JN	1
109	12	IG,EA,KF,AC,JL,IL,HE,DC,ID,AG,KE,AH,GE,ED	0
110	8	GB,CD,GC,EC,FH,AD,FC,AH,FD,BC,HB,GF,HC,DG	0
111	10	AG,AC,IA,BF,JF,JB,DB,DH,FD,EI,GI,HJ,HF,EA,GC,CE,GE,BH,DJ,IC	2
112	12	HL,JA,EB,DG,CG,AI,FB,HK	2
113	10	EA,DJ,EI,FJ	2
114	14	BC,AN,JI,LM,ED,HI,BA,DC,KJ,KL,GH,EF,MN,FG	14
115	6	CF,FE,EA,DE,AD,DB,FA,CE,FD,DC,AB,AC,CB,BE,FB	6
116	9	DG,CG,GF,FC,GB	0
117	12	HI,LH,AL,IA,EK,DJ	1
118	8	BC,CD,CG,GF,BA,BF,EA,DH,ED,EF,AH,HG	8
119	9	DF,CD,GF,AH,EC,BA,IB,EG,ED,FH,EF,IG,BC,AI,GH,BD,HI,AC	9
210	15	JK,MC,LG,HC,BG,BL,HM,AO,FE,ON,DE,IJ	3
211	9	IF,FH,BH,EG,BE,AG,EC,AH,DG,DH,FC,IE,CI,DI,AF,BF,EA,CG,CA,BI,GB,HE,FD,DB,IG,DA,CH	9
212	20	SA,FA,MH	0
213	6	AC,FD,CE,BF	2
214	14	NI,BJ,JL,DJ,GN,DM,IC,FK,HJ,MF,CA,GB,CK,CE	2
215	15	LI,FC,AD,MA,OC,MJ,GJ,FI,DG,LO	5
216	8	HF,CE,CB,HE,AC,AF,AG,ED,HB,GF,EB,AH,DG,DB,HC,DA,GE,DF,GB,FC	4
217	8	HF,FD,EH,AH,CD,DG	1
218	10	FJ,HD,IC,GC,AG,JD,FB,BH,EA,EI	10
219	15	FN,NG,BI,ME,BJ,LM,AH,OA,IJ,DK,LE,GF,HO,DC,CK	5
220	20	QR,OQ,GK,JR,FD,AM,OP,NE,FT,IA,JK,IO,LH,RG,DT	0
221	7	FA,CF,DA,DB,FD,DG,AG,EB,AE,CG,BG,FG,BF,BA	1
222	9	GI,HA,CG,AE	3
223	10	FG,HB,GC,GA,BC,BA,BE,IB,GB,JG,BF,JD,IE,GD,GH	2
224	16	LK,MN,OJ,KE,ME,JE,MJ,NL	0
225	20	RH,ML,GR,DR,BC,BT,KQ,OM,GQ,PC,HQ,EJ,TH,OG,MR,BQ,SL	1
226	10	CD,GH,CB,HI	2
227	9	CA,BC,DF,BG,BD,EG,ED,GC,HI,EF,ID,AH,IB,EC,GI,EA,IA	1
228	12	KL,JA,EC,AC,GF,EH	1
229	9	BC,GF,IH,ED,IB	1
320	12	CE,HD,HF,AC,HL,IB,CL,CF,DL,IG,BF,IK,JL,FJ,JB,ID	1
321	9	BC,CH,GA,AE,FI,DI,AB,HG,BF,HI,DA,DE,FE,DH,AF,GB,CF,CI,CG,GD,EI	0
322	8	DE,AF,HB,FB,FD,EB,HG,AB,DC,BC,FC,CE,AG,GF,GC,BG,FE,GD,CH,AH	2
323	8	FE,CG,EA,DH,GH,DC,FB,AB	4
324	12	FL,GA,LG,DB,LJ,JD,CD,LB,CL,IA,IC,CG,EK,KI,KH	0
325	16	CM,HC,EJ,NE,GP,LD,FM,IA,PK,IB,OH,DK,MB,JP,JA,BH,LC,KE,NF,OG	2
326	10	AI,BE,CI,AH,DJ,JG,FC,GI,IE,BD,DF,HD	2
327	9	GF,CD,FB,GB,EH,IE,HG,IC,AC,IA,GE,CE,AF,IG,ED,BA,HA,CH	1
328	7	DE,AG,AB,BG,EB,FG,AD,FD,FE,EG,AF	1
329	12	EA,KD,FC,KF,EG,DH,BL,CK,KI,JA,BC,AK,JG,GF,EI,JB,LH,LA,LC	0
330	9	AI,GB,HI,CG,DE,BC,EB,FE,IC	1
331	12	JE,DH,IA,JB,LG,GC,AF,DK	2
332	12	AI,FB,LK,HD,IK,KB,LH,KG,LC,DA,FA,JD,DC,KE,IE,IB,JF,CG,FD	1
333	6	BE,CF,AD	2
334	14	AL,DN,IL,NK,AC,LH,FE,CF,NC,FG,FI,IK	1
335	10	CG,EA,EI,CI,AG	5
336	14	EH,GB,DM,NI,CL,AD,KN,JA,HC,KB,LG,JG,NE,DI,FC,KF,EJ,MB,IL,MH,AF	7
337	12	LH,JB,JG,BF,AJ,LI,KC,LC,KG,GD,AE,IE,FC,FI,DA,DH	4
338	10	AH,CG,CF,EB,AG,DG,BI,IF,DA,ID,CI,EJ,HE,IE,FA,HC,EA,JG,CJ,BG	5
339	9	HB,BG,AE,AD	1
430	10	EJ,BE,FC,CG,FD,JI,IG,CH	0
431	9	IE,FH,EA,ED,BD,EF	1
432	12	AL,IE,JL,JE,GF,AB,FK,GL,JH,GC,AH,EA,BG,KL,DF,DH,CE,HB,FB,CA,CK,IB	1
433	14	EF,LA,GI,BM,GE,KM,CA,HI	1
434	16	AG,KM,AI,CA,MF,HE,DN,OH,DJ,JK,LO,CJ,FC,LH,AB,GP,EA,HB,GL,PI,HF,FB,KP,BD,CB,BM	0
435	20	HI,GH,CB,IM,SR,QM,LM,SC,RN,DH,HL,RB,NM,GC,QR,DC	4
436	15	CE,JM,GJ,NB,OD,EF,NE,KG,GL,BO,HF,EJ,MA,CO,HN,DN,GA,AI,BG,HL,EO,IO,MK,ED,JO,AB,AF,MO,FK	0
437	22	TN,IC,NG,RC,HB,DS,OH,MS	2
438	16	EC,MK,HF,PN	2
439	14	HL,IB,JN,ND,JF,HA,LB,HD,EL,BF,DK,MF,NG,CJ	7
440	9	AE,BF,IE,DC,HG,ED,HD,DI,EF,CH,GB,GF,IA,BC,AF,CG,HI,AB	9
441	10	ID,HG,BE,CI,FJ,FI,GB,AH,DG,CJ,IJ,HD,HC,BF,AF,CG,EA,EJ,IE,JD,BH,DC,AB,FE,GA	5
442	8	BF,AE,HD,CG	8
443	8	EA,GF,FD,GB,BD,FH,FE,CA,CG,HA,AG,GH,HD,BC,BH,CH,GE,EB,DA,FC,AB,FA,CE,BF,ED,GD	0
444	20	IM,EN,PA,EI,IH,MD,QB,HQ,KI,NR,JI,RO,JA,CT,TD,IG	4
445	15	DC,JL,CK,HG,NO,JA,BK,FD,HI,BF,NJ,ML,AM,EF,FK,JO,CO,NE,EJ,AB,BJ,FA,FO,NF,ME,KJ	1
446	16	JA,MI,OE,MH,EP,LN,PD,PA,CP,OA,LC,HN,MJ,LM	1
447	12	JG,EB,BI,DH,IJ,DI,BJ,IH,HK,DA,AE	1
448	14	FI,MA,BA,LH,HA,DI,BF,EB,IK,CA,ND,EK,NB,JH,NL,JE,EF,BI,KA,CG,LE,KN,KD,EA,NG,DF	0
449	8	EF,CG,GH,EC,BG,GF,EG,BE,DE	0
540	8	CB,CA,GA,CE,FD,EB,GC,GF,HA,FE,HG,HE,CD,AF,HB,BA,AE,GE,DA,DE	2
541	10	AC,EC,HJ,FH	2
542	15	ME,JC,IO,JM,OH,DJ,EH,NE,NK,CO,IF,AI,NF,DA,DK	3
543	12	HB,GI,FH,EC,AK,BG,IH,CJ,DK,AC,FE,FL,KI,LJ,HC,DJ,LA,FK,GE,LG,DE,BD,IJ,AB	6
544	18	JM,DA,DR,DI,BG,PK,GC,BC,PA,RM,JG,HD,LK,IM,GK,PB,PL,RQ,IH,QM	2
545	15	NH,CB,CI,BK,ML,AG,MD,FL,GH	3
546	10	HB,BF,ID,HG,HC,GF,IA,JE,CD,IC,EA,AF,CE,AJ	1
547	16	HO,PL,LN,MA,BF,PK,LE,KD,GN,CN,GB,GD,EA,KN,DO,MF,CJ,FD	1
548	18	RH,OH,FD,PL,MI,CG,PN,DM,CL,IQ,QA,JH,BR,MO,GE,HA,HP,GQ,QF,FH,ML,JL,AC,QO,DC,JQ,DR,KI	2
549	18	HP,LF,OL	0
550	10	AI,DF,EC,JH	2
551	16	PG,PE,MO,DI,MP,KH,JC,LE,KC,MF,OP,NG,HA,DJ,EB,CO,MH,GJ,IC,NM,JB,NP,AI,CF,OF,DL,NJ	1
552	14	BF,LN,HA,CE,GC,KA,BI,KM,FD,JN	1
553	18	JL,KH,KF,BI,QN,OH,FB,EB,LQ,LO,MK,RP,KO,RC,AQ,RN,EG,IF,ER,DF,CN,QC,HL,EI	3
554	19	PH,AS,EP,SH,AL,DL,OD	1
555	10	GE,ID,JH,IE,AF,GC,FJ,HB	10
556	18	FB,MC,BD,KA,NR,OG,OJ,AI,DI,LH,FD,KP,PR,HJ,ME,PC,QG,QD,PN,JL,EJ	3
557	18	QM,GI,FB,DC,KI,PL,EC,AE,OM,PC,RI,BO,ON	1
558	21	BF,AR,DJ,LN,ON,UC,DI,BR,LM,MO,IE,FC,JT,UD,GQ,QB	1
559	9	FG,BA,HI,FE,DA,EI,HE,GH,HF,DC,IG,IC,ID,GC,DH,IA,IB,CA,DG,BH,BE,FB,AF,DE,AG	0
650	16	PI,MD,JA,CH,CN,AH,LE,GB,IB,FK,KP,OJ,NE,OD,LG,MF	4
651	25	MA,CG,LE,EQ,AK,XO,RI,VT,WU,KO,XQ,AS,YI,MF,QG,CS	1
652	12	FG,HG,DH,BA,BF,BC,LA,IH,LH,CD,JF,JB,JI,DL	2
653	15	KD,AN,LC,GJ,AE,CG,IO,EK,DM,AO,HB,HG,KM,HF,DI,LO,MC,JE,JN,GM,MA,LM	0
654	15	OA,EG,OG,JK,OH	3
655	16	CN,IH,HG,IM,BK,AJ,LF,GC,MB,OK,FH,NE,FA,DL,HJ,EP,OF,JO,KP,JD,AE	1
656	12	AB,EC,IK,FD,EH,DB,BK,AD,HJ,GE,FC,CI,GJ,LF,AI,LJ,IL,FB,KA,GC,GH,HL	2
657	20	IS,AK,EO,FP,RH,TJ,LB,DN,CM,GQ	20
658	15	EK,BC,JK,CL,GM,AO,AJ,HG,HB,OF,LM,FE	3
659	10	AB,GF,IH,DI,BG,IJ,CB,GH,ED,CD	2
660	10	HC,AC,EA,JD,BD,FH,HA,IE,GE,AF,GC,CB,AJ,HB,DG,JH,CJ,IC	0
661	22	IE,KT,JB,QC,NF,ER,PB,LV,VR,UM,BI,IV,IR,TM,PG,PD,RC,AK,KC,ME,TG,NV,TP,KG,EO,NG	2
662	22	TH,UI,GB,VE	1
663	18	NO,FG,KF,OJ,RA,LQ,QA,JH,PC,RE,ML,GE,NP,HI,ID,DB,CB,KM	3
664	25	KF,BL,FL,IA,MC,UM,BS,MG,IR,IC,BH,FV,DI,FN	1
665	15	DK,IB,LD,GF,LA,FJ,BA,KG,FN,BM	1
666	10	ED,GH,EF,CB,IJ,JA	1
667	12	HL,FB	2
668	10	FE,HG,FJ,JI,JD,IF,AC,JH,BJ,HI,AG,JC,CG,IG,AH,EG,DG,FD,BA	1
669	21	QC,KD,PB,ES,HO,AH,LE,KR,NG,FT,MT,IB,UN,JQ	7
760	21	RJ,CK,FN,TL,SF,IQ,LD,AI,CP,HU,RE,OB,GO,UM	7
761	18	OH,LA,GR,CN,MF,BI	3
762	24	BM,VK,JV,MJ,OM,HK,WO,RE,UO,TW,XQ	0
763	15	NI,FM,OG,ND,HM,LB,JC,EO,CH,BG,KA,IA,JE,DL,KF	5
764	18	QD,FE,RN,JG,IE,LK,ID,NF,JR,HA,IP,CB,LA,CM,EH,LJ,AK,QL,KD	0
765	18	JQ,IB,AH,NA,EJ,IN,ER,RK	3
766	15	AO,CG,CH,AD,ND,GE,OD,OB,FC,FG	1
767	26	XF,EW,HP,PX,MU,RZ,YG,KS,IQ,IA,KC,BJ,OG,YQ,HZ,DV,EM,WO,SA,LD,JR,BT,UC,NV,TL,FN	26
768	14	GN,BI,KG,GB,JM,IE,IN,CF	1
769	20	EP,QM,CG,MD,NC,OF,FB,PL	2
770	20	NJ,LM,OP,RN	1
771	15	MJ,BM,NH,NC,MD,LC,MA,HE,IC,HL,HD,CG,IM,HK,HB,OC,MG,CF	3
772	20	MT,JS,EB,LJ,ND,GT,AE,QH,PF,OS,AJ,HJ,GF,RO,LC,NM	1
773	21	NC,KU,QG,ND,JU,RG	3
774	11	KF,EF,HF,KD,DB,GI,BK,JI,DI	1
775	15	LI,GD,BN,EF,IH,LO,DC,MN,EB,OA,GJ,KJ	3
776	14	HI,DE,KJ,ML,BC,AN,FG	7
777	14	DA,NE,KH,GL	7
778	21	LU,SJ,SI,FU,BF,RP,EM,OG,NB,ER,RM,OB,UO,FK,GR,NS,BJ,KJ,UQ,KB,TA,CK,LE,OJ,QO	0
779	16	KG,FG,IM,EF,EA,JB,ON,JP,BL,MN,DJ,BH,OC	2
870	12	DJ,HC,EJ,HE,IB,KH,IF,DK,AG,CI,DG,FC,KB,DA,FA,LG,EB,AJ,GJ,CL,EK,LI,HB,FL	6
871	20	AI,OP,KR,AM,CK,DS,JR,EP,DK,IN,HM,HA,NA,DL,QP,FG,FO,PG,BN,RC,QF,SK,HT,EF	2
872	15	AO,GH,KL,JI,GF,BC,FE,AB,ML,JK,ED,HD,MI,NO,NC	3
873	20	HL,CG,RB,MQ	4
874	12	EH,BK,AI,FJ	1
875	21	GB,UE,AR,OI,AF,IE,OR,DT,IL,AS,SI,LK,OP,HR,CT,HE,RL,CG	1
876	14	NF,EA	14
877	15	CN,JN,EL,CI,LA,BA,FJ,IJ,LI,HL,HB,NF,NB,AE	1
878	21	HR,QO,GP,RQ,GA,PO,GH,KM,SO,KU,BG,BR,AJ,TU	0
879	14	MJ,BC,BG,HN,DA,KC,GL	0
880	16	PH,DF,IA,IK,MK,NP,OA,GE,MO,GI,DB,OG,JH,FH,AC,PB,EM,LJ,LN,FN,LD,EC,CK,JB	16
881	18	FJ,IC,LO,NH,KG,BE	1
882	16	HC,FG,JC,ON,ID,MF,NM,KB,IB,FE,PE,PK,LG,OD,BA,JK,CB,LA,NE,MH,AJ,FO,IJ,GN	4
883	18	AG,EJ,CN,NI,RL,PE	1
884	18	EC,ID	0
885	15	AK,HD,DE,GO,HA,ME,AL,AG,OC,FG,JK,KN,IM,KD,CH,OI,AF,MJ,GK,LD,IB,KL,AI,JN,FE,MF,IG	0
886	26	SX,IW,FA,RQ,UJ,FK,MX,HW,KZ,KY,FW,VJ,BG,JS,ED,XL,SN,JO,CD,BK,XO,PQ,TO,WB	2
887	22	FG,MS,AQ,ER,RI,DR,RJ,HG	1
888	14	KB,CM,EI,BL,FJ,DI,FK,MD	1
889	14	HI,KE,FJ,HC,FI,ID,HD,KC,GD,LC,JE,CN,EM,JL,KJ,MI	0
980	20	RQ,GH,TS,QP,DE,NO,BC,EF,IH,FG,LK,JI,AT,SR,DC,LM,MN,OP,KJ,BA	20
981	20	CQ,RE,GP,RK,KI,HM,GL,KC,LA,CJ,DP,AP,JQ,ML,KE,OP,TO,LP,LI,LD,PS,KD,SQ,QE,DQ	1
982	15	DC,ME,KL,GF,KA,BJ,HI,EA,JN,DN	1
983	13	HM,MC,CG,LC,EJ,IA,CF,FK,CD,CB	1
984	14	MG,GJ,EM,HE,AG,JM,IA,DG,IC,NK,KH,CN,DA,CK,BM,BE,FC,AL,IL,EK,IF	7
985	22	TG,DM,JA,NA,CP,TK,VM,JS,HU,IV,LU,DQ,SF,LC,OB,EN,OF,HQ,RE,KB,PG,RI	22
986	22	IU,NU,UK,RK,DV,JC,TO,CT,HO,IQ,VT,JM,HJ,DU,IB,BH,GN,IE,IJ,DT,GK,RN,HS,ON,PU,PI	0
987	14	CM,JG,KB,BL,JE,KG,GF,BC,GL,HN,GB,AI,IC,AE,NF,DM,JH,EC,FJ,MI,FD,DJ,EM,KM,JL,NJ,DH,MB,MA	2
988	24	OI,SP,LI,MS,KL,QP	1
989	15	DF,KN,LJ,FI,DA,GE,AG,OB,LO,GJ,OI,NE,JD,LF,BE,IK,BK,NA	3
990	16	HG,BD,IA,MK,PG,MB,KP,AL,LB,GB,GJ	0
991	20	IL,FM,PE,HR,PM,QC,ER,HB,QG,LS,IT,GT	1
992	20	NA,CJ,IP,SL,QJ,PC,IB,DK,DQ,TG,RK,GN,HO,MT,OB,FS,MF,RE,LE,HA	20
993	18	QM,EA,CQ,RG,OD,OK,JC,PI,EI,GK,FM,AL	3
994	15	DL,NH,DC,IH,OM,MD,JE,BG,OH,NL	1
995	21	BD,UQ,HC,NS,NR,PC,AE,EM,JD,HN	0
996	15	NJ,OB,GE,KF,LB,KM,LJ,EI,AK,OK,GL,AC,FJ,DH,FH,DO,HL,FA,CN,GC,AE,GB,MB,MI	3
997	21	AE,OS,FT,UQ,NT,AL,PT,IP,OE,BH,MT,BF,IM,IO,MF,AP,FU,NJ,UJ,LH,QG,SH,CG,MG,BP,CN,BI	3
998	21	PR,SR,FK,ME,KI,AO,GL,SF,LH,DU	0
999	25	ID,DX,XS,NI,NS	1
stdout
× (10) 111	10	AG,AC,IA,BF,JF,JB,DB,DH,FD,EI,GI,HJ,HF,EA,GC,CE,GE,BH,DJ,IC	2
× (1) 222	9	GI,HA,CG,AE	3
× (3) 321	9	BC,CH,GA,AE,FI,DI,AB,HG,BF,HI,DA,DE,FE,DH,AF,GB,CF,CI,CG,GD,EI	0
× (6) 333	6	BE,CF,AD	2
× (0) 432	12	AL,IE,JL,JE,GF,AB,FK,GL,JH,GC,AH,EA,BG,KL,DF,DH,CE,HB,FB,CA,CK,IB	1
× (1) 444	20	IM,EN,PA,EI,IH,MD,QB,HQ,KI,NR,JI,RO,JA,CT,TD,IG	4
× (3) 543	12	HB,GI,FH,EC,AK,BG,IH,CJ,DK,AC,FE,FL,KI,LJ,HC,DJ,LA,FK,GE,LG,DE,BD,IJ,AB	6
× (1) 555	10	GE,ID,JH,IE,AF,GC,FJ,HB	10
× (0) 654	15	OA,EG,OG,JK,OH	3
× (2) 666	10	ED,GH,EF,CB,IJ,JA	1
× (2) 765	18	JQ,IB,AH,NA,EJ,IN,ER,RK	3
× (2) 777	14	DA,NE,KH,GL	7
× (1) 876	14	NF,EA	14
× (2) 888	14	KB,CM,EI,BL,FJ,DI,FK,MD	1
× (1) 987	14	CM,JG,KB,BL,JE,KG,GF,BC,GL,HN,GB,AI,IC,AE,NF,DM,JH,EC,FJ,MI,FD,DJ,EM,KM,JL,NJ,DH,MB,MA	2
× (5) 999	25	ID,DX,XS,NI,NS	1