QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#98692#6329. Colorful GraphCSU2023AC ✓543ms21292kbC++144.7kb2023-04-19 20:34:472023-04-19 20:34:50

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-19 20:34:50]
  • 评测
  • 测评结果:AC
  • 用时:543ms
  • 内存:21292kb
  • [2023-04-19 20:34:47]
  • 提交

answer

#include <bits/stdc++.h>

template <class T>
inline void read(T &res)
{
	char ch; bool flag = false; res = 0;
	while (ch = getchar(), !isdigit(ch) && ch != '-');
	ch == '-' ? flag = true : res = ch ^ 48;
	while (ch = getchar(), isdigit(ch))
		res = res * 10 + ch - 48;
	flag ? res = -res : 0;
}

template <class T>
inline void nonnegative_put(T x)
{
	if (x > 9)
		nonnegative_put(x / 10);
	putchar(x % 10 + 48);
}

template <class T>
inline void put(T x)
{
	if (x < 0)
		x = -x, putchar('-');
	nonnegative_put(x);
}

template <class T>
inline void CkMin(T &x, T y) {x > y ? x = y : 0;}
template <class T>
inline void CkMax(T &x, T y) {x < y ? x = y : 0;}
template <class T>
inline T Min(T x, T y) {return x < y ? x : y;}
template <class T>
inline T Max(T x, T y) {return x > y ? x : y;}
template <class T>
inline T Abs(T x) {return x < 0 ? -x : x;}
template <class T>
inline T Sqr(T x) {return x * x;} 
//call Sqr((ll)x) when the type of returned value is "long long".

using std::map;
using std::set;
using std::pair;
using std::bitset;
using std::string;
using std::vector;
using std::complex;
using std::multiset;
using std::priority_queue;

typedef long long ll;
typedef long double ld;
typedef complex<ld> com;
typedef pair<int, int> pir;
const ld pi = acos(-1.0);
const ld eps = 1e-8;
const int Maxn = 1e9;
const int Minn = -1e9;
const int mod = 998244353; 
const int N = 14e3 + 5;

vector<int> e[N];
vector<pir>re[N];
int sre[N], lre[N], ans[N], ind[N], dfn[N], low[N], stk[N], col[N]; 
bool ins[N];
bitset<N> vis[N];
int T_data, n, m, C, top, tis;

const int M = 7e4 + 5;
int nxt[M], to[M], cap[M], adj[N], que[N], cur[N], lev[N];
int src, des, qr, T = 1;

inline void linkArc(int x, int y, int w)
{
	nxt[++T] = adj[x]; adj[x] = T; to[T] = y; cap[T] = w;
	nxt[++T] = adj[y]; adj[y] = T; to[T] = x; cap[T] = 0;	
}

inline bool Bfs()
{
	for (int x = 1; x <= des; ++x)	
		cur[x] = adj[x], lev[x] = -1;
	// 初始化具体的范围视建图而定,这里点的范围为 [1,n]
	que[qr = 1] = src;
	lev[src] = 0;
	for (int i = 1; i <= qr; ++i)
	{
		int x = que[i], y;
		for (int e = adj[x]; e; e = nxt[e])
			if (cap[e] > 0 && lev[y = to[e]] == -1)
			{
				lev[y] = lev[x] + 1;
				que[++qr] = y;
				if (y == des)
					return true;
			}
	}
	return false;
} 

inline int Dinic(int x, int flow)
{
	if (x == des)
		return flow;
	int y, delta, res = 0;	
	for (int &e = cur[x]; e; e = nxt[e]) 
		if (cap[e] > 0 && lev[y = to[e]] > lev[x])
		{
			delta = Dinic(y, Min(flow - res, cap[e]));
			if (delta)
			{
				cap[e] -= delta;
				cap[e ^ 1] += delta;
				res += delta;
				if (res == flow)
					break ; 
				//此时 break 保证下次 cur[x] 仍有机会增广 
			}
		} 
	if (res != flow)
		lev[x] = -1;
	return res; 
}

inline int maxFlow()
{
	int res = 0;
	while (Bfs())
		res += Dinic(src, Maxn);
	return res;
}

inline void Tarjan(int x)
{
	dfn[x] = low[x] = ++tis;
	stk[++top] = x;
	ins[x] = true; 
	for (int y : e[x])
		if (!dfn[y])
		{
			Tarjan(y);
			CkMin(low[x], low[y]);
		}
		else if (ins[y])
			CkMin(low[x], dfn[y]);
	if (dfn[x] == low[x])
	{
		int y;
		++C;
		do
		{
			y = stk[top--];
			ins[y] = false;
			col[y] = C;
		}while (y != x);
	}
}

int main()
{
	read(n); read(m);
	for (int i = 1, x, y; i <= m; ++i)
	{
		read(x); read(y);
		e[x].emplace_back(y);
	}
	for (int i = 1; i <= n; ++i)
		if (!dfn[i])
			Tarjan(i);
	for (int x = 1; x <= n; ++x)
	{
		for (int y : e[x])
			if (col[x] != col[y])
				vis[col[x]][col[y]] = 1;
		e[x].clear();
	}
	src = (C << 1) | 1, des = src + 1;
	for (int x = 1; x <= C; ++x)
	{
		linkArc(src, x, 1);
		linkArc(x + C, des, 1);
		linkArc(x + C, x, Maxn);
		for (int y = 1; y <= C; ++y)
			if (vis[x][y])
				linkArc(x, y + C, Maxn);
	}
	int _ans = maxFlow();
	for (int x = 1; x <= C; ++x)
		for (int e = adj[x]; e; e = nxt[e])
			if (to[e] > C && to[e] < src && to[e] - C != x && cap[e ^ 1] > 0)
			{
				re[x].emplace_back(std::make_pair(to[e] - C, cap[e ^ 1])); //保证空间复杂度严格正确
				++lre[x];
				sre[x] += cap[e ^ 1];
				ind[to[e] - C] += cap[e ^ 1]; 
			}
	tis = 0;
	for (int t = 1; t <= C; ++t)
	{
		for (int x = 1; x <= C; ++x)
			while (sre[x] > ind[x])
			{
				++tis;
				int u = x;
				ans[u] = tis;
				while (sre[u])
				{
					pir &v = re[u][lre[u] - 1];
					int vid = v.first;
					if (--v.second == 0)
						re[u].pop_back(), --lre[u];
					--sre[u];
					u = vid;
					ans[u] = tis;
					--ind[u];
				}
			}
	}
	for (int x = 1; x <= C; ++x)
		if (!ans[x])
			ans[x] = ++tis;
	for (int i = 1; i <= n; ++i)
		put(ans[col[i]]), putchar(' ');
	putchar('\n');
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4152kb

input:

5 5
1 4
2 3
1 3
2 5
5 1

output:

1 1 1 2 1 

result:

ok AC

Test #2:

score: 0
Accepted
time: 0ms
memory: 8140kb

input:

5 7
1 2
2 1
4 3
5 1
5 4
4 1
4 5

output:

2 2 1 1 1 

result:

ok AC

Test #3:

score: 0
Accepted
time: 2ms
memory: 5540kb

input:

8 6
6 1
3 4
3 6
2 3
4 1
6 4

output:

1 1 1 1 2 1 3 4 

result:

ok AC

Test #4:

score: 0
Accepted
time: 397ms
memory: 17848kb

input:

7000 6999
4365 4296
2980 3141
6820 4995
4781 24
2416 5844
2940 2675
3293 2163
3853 5356
262 6706
1985 1497
5241 3803
353 1624
5838 4708
5452 3019
2029 6161
3849 4219
1095 1453
4268 4567
1184 1857
2911 3977
1662 2751
6353 6496
2002 6628
1407 4623
425 1331
4445 4277
1259 3165
4994 1044
2756 5788
5496 ...

output:

1 1657 1326 1564 1746 2 3 1365 1110 1505 1750 1750 4 1750 1519 5 516 6 1061 25 1257 585 1747 1498 1662 7 8 1730 1404 9 1171 1198 10 11 1357 1358 286 12 1747 13 1525 1158 14 534 15 687 16 1747 17 18 890 19 1292 1746 1647 187 1747 20 1031 21 1192 1746 1746 1747 158 22 1747 1747 1506 23 24 710 25 981 2...

result:

ok AC

Test #5:

score: 0
Accepted
time: 466ms
memory: 19340kb

input:

7000 6999
4832 1603
5984 6985
5355 3687
6007 2170
5984 3486
3267 2189
538 2123
4343 4553
5855 6168
5984 257
4239 2304
5984 2063
3298 1869
5984 6353
5984 2018
5984 5387
5984 3382
3164 3978
2690 2816
4810 2638
5984 3773
5984 1634
5984 2786
5984 3671
5984 5140
2943 5721
5984 414
1105 4060
3093 796
5984...

output:

2332 2332 618 465 1723 2332 886 671 2332 2324 2324 2332 2332 1274 2333 1 2332 2332 2332 2330 2 1713 2095 1232 2332 2332 848 1896 782 1568 1664 2332 2332 2332 3 4 1371 2332 117 135 5 237 1187 6 1846 7 21 8 9 1573 18 1533 2303 204 1811 2332 10 11 12 13 2332 2332 14 2324 805 1558 2332 617 2332 2264 15 ...

result:

ok AC

Test #6:

score: 0
Accepted
time: 543ms
memory: 19292kb

input:

7000 6999
1649 5337
1701 3344
4394 2172
3330 39
5932 1141
5381 5340
5453 3300
125 2172
6810 5263
804 2172
6635 2172
676 4740
3015 1183
1710 5769
611 5915
3419 1581
2094 2172
4508 2172
6604 2433
6113 1466
1604 696
1518 1123
1287 2940
4825 2172
5130 4524
2693 2172
106 2172
5157 2172
3693 2172
5198 217...

output:

1 2 464 319 2256 3 165 1084 1720 4 1209 5 6 1456 1755 529 7 385 1158 1690 1683 8 9 1446 1840 266 1643 413 10 11 1792 12 1334 1621 1410 13 1970 421 94 14 2126 2073 1741 15 1998 1177 1705 303 16 2298 377 17 1672 1538 1695 323 2043 18 583 2329 19 2282 20 2183 1827 1894 221 813 21 22 23 24 25 1078 1909 ...

result:

ok AC

Test #7:

score: 0
Accepted
time: 188ms
memory: 19212kb

input:

7000 6999
2896 6321
881 2623
5058 2623
4833 2623
4669 2623
4781 5007
1447 2623
4781 4768
4781 3834
2758 4792
797 5055
3784 2623
4781 5510
6606 3040
597 3459
4136 2037
1291 3989
4781 837
4781 4379
5637 2053
1642 2665
4781 4664
4781 952
4924 2511
4781 4201
4781 2352
4781 5362
3901 197
137 2623
2706 19...

output:

1 1750 1750 1750 1750 1750 1750 2 354 3 1750 1750 1750 1750 1750 1443 1548 1750 1750 4 1345 1750 795 607 1367 1504 1428 1007 5 6 1750 7 1750 1750 1750 1750 1536 226 1750 699 1750 1750 879 1750 8 1750 9 1750 10 1750 1750 1750 11 12 1750 13 1750 1750 783 1750 14 1750 1750 113 1750 15 272 1499 1750 174...

result:

ok AC

Test #8:

score: 0
Accepted
time: 81ms
memory: 14852kb

input:

6999 6998
1269 3969
1269 2429
1269 2609
1269 2515
1269 6166
1269 6614
3108 1269
2105 1269
4670 1269
578 1269
4661 1269
1421 1269
2576 1269
6152 1269
1269 6636
3011 1269
305 1269
5189 1269
1683 1269
6861 1269
1269 5798
1499 1269
282 1269
914 1269
80 1269
677 1269
701 1269
1269 359
6521 1269
1269 1754...

output:

1 2 3 4 1073 5 6 2667 1045 3245 3304 2946 7 434 8 9 10 976 11 12 125 13 14 2692 15 16 17 18 19 1675 20 1067 21 22 3194 23 1614 459 24 515 971 25 26 1204 3088 27 28 29 30 31 2522 1552 3493 32 263 2395 33 34 35 36 37 577 20 38 3396 2833 3337 39 40 41 525 42 730 1745 2103 43 44 2792 45 46 2095 47 2380 ...

result:

ok AC

Test #9:

score: 0
Accepted
time: 86ms
memory: 6356kb

input:

7000 0

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...

result:

ok AC

Test #10:

score: 0
Accepted
time: 88ms
memory: 17796kb

input:

7000 6999
3138 1903
3285 5919
6182 1430
1164 961
1577 6445
1390 3384
935 5723
6614 6387
4799 2877
3915 5128
5366 5455
2287 3941
2053 2326
4022 6993
488 2922
4327 4701
4674 3221
1666 4773
4356 3232
3888 937
4318 6942
577 1299
4491 1938
5154 1254
790 5532
4286 5478
2918 6725
2853 304
2554 5207
5140 77...

output:

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

result:

ok AC

Test #11:

score: 0
Accepted
time: 16ms
memory: 13004kb

input:

7000 6999
33 3147
5877 4807
3116 4168
1651 2456
624 1740
6440 3058
6414 489
1023 2523
706 93
5523 598
4211 6063
3570 6840
6566 2971
6614 1907
5893 4389
4022 2527
5096 2345
4682 2134
188 5597
695 4285
1344 3832
3534 879
6574 6252
3759 3444
2167 85
5630 6600
3158 4404
6389 689
4871 6719
4295 6008
3437...

output:

18 20 32 32 16 16 32 29 32 32 32 32 32 34 32 29 32 17 32 32 9 32 20 32 32 32 32 32 32 32 32 32 35 32 32 29 3 13 32 32 32 16 7 32 1 32 9 32 32 29 32 32 32 32 32 29 32 32 32 19 9 3 3 32 32 32 32 33 20 32 28 20 32 32 16 32 22 33 20 32 18 12 32 32 6 24 32 32 12 32 20 32 32 32 32 14 36 32 6 32 32 32 32 1...

result:

ok AC

Test #12:

score: 0
Accepted
time: 11ms
memory: 10740kb

input:

7000 6999
1247 5150
3318 2013
5686 1615
6145 6521
5717 94
2787 3443
2648 4875
5332 5934
1897 1651
4640 2183
1750 6964
148 5228
745 2814
474 1165
496 6735
180 3412
2723 3374
6200 4361
497 5328
1928 5998
5648 1261
5090 4723
1715 706
2499 897
6569 6204
6039 2787
2882 5044
5767 4256
975 1877
1857 4453
6...

output:

85 86 85 21 85 85 26 85 72 85 5 80 27 85 85 28 85 85 85 85 85 85 85 85 85 85 69 85 44 87 85 85 85 85 85 85 64 85 37 85 85 85 71 85 85 21 85 85 85 57 76 88 85 85 85 85 85 17 5 85 21 32 85 85 85 80 85 85 7 34 85 84 44 85 85 85 85 85 1 24 85 85 85 85 85 21 85 85 85 85 7 85 85 85 10 85 85 85 85 85 57 85...

result:

ok AC

Test #13:

score: 0
Accepted
time: 43ms
memory: 14304kb

input:

7000 6999
2349 199
5295 2831
6143 2006
3212 3198
6956 3807
732 4838
5069 1027
5744 3479
6 5301
5687 4452
4201 1151
1353 4884
548 3506
6094 4799
4950 6939
5234 817
652 1314
979 6984
5771 1851
398 1322
2294 4298
847 3929
6833 183
2904 6745
4797 3874
94 315
4282 582
6591 5037
962 147
799 908
2593 5547
...

output:

618 619 66 618 618 196 512 320 385 138 216 618 607 192 556 618 387 391 1 232 584 618 618 2 490 618 618 3 255 618 170 445 428 142 618 249 618 593 358 127 543 618 220 443 618 4 581 618 618 5 489 262 6 7 559 620 138 233 8 440 618 618 149 618 618 519 66 210 61 211 618 618 618 618 607 618 409 618 212 97 ...

result:

ok AC

Test #14:

score: 0
Accepted
time: 67ms
memory: 17544kb

input:

7000 6999
3409 1629
2076 6412
4997 1078
6320 626
4501 1104
4173 1774
5507 2375
2299 5115
4321 127
1192 6635
1909 3398
2972 499
862 5024
421 2931
861 1536
902 3813
659 4514
1843 3035
3669 1228
1724 1880
34 706
133 3468
6116 585
5073 1461
5667 3405
715 4834
6915 3007
1736 6108
3264 2870
2393 6474
2108...

output:

406 1661 1 938 1661 2 527 1661 1084 3 877 4 1661 5 1676 1510 73 1661 525 1041 1661 6 1661 959 7 1661 8 1677 1678 1679 1661 9 1661 1680 52 484 1183 824 10 575 1352 731 144 283 1661 49 142 248 1681 1465 303 753 1661 1265 1661 1537 453 1592 11 12 1381 1661 465 13 1481 1682 66 1683 1415 1684 365 615 14 ...

result:

ok AC

Test #15:

score: 0
Accepted
time: 107ms
memory: 19168kb

input:

7000 7000
2048 5882
6801 2408
3225 2608
1441 5079
497 6253
557 5589
2535 6257
4800 2595
4713 1286
4759 6636
4303 4296
6195 2048
6994 2987
1249 3044
1036 10
6472 2076
1996 1086
1279 1486
6100 369
4797 3437
2493 4576
2944 5601
197 5582
5488 5035
4023 659
2651 5024
2257 5710
1001 3941
446 4815
687 702
...

output:

1761 1 2 1762 1763 3 1137 1766 1767 324 5 268 8 1072 1632 1308 14 1781 483 1545 587 15 439 423 16 98 272 765 18 759 22 23 1483 906 912 24 25 1788 814 1789 26 27 1790 648 606 28 1791 401 798 157 1793 105 29 515 1794 840 1795 1230 32 1518 1796 382 1459 33 505 34 533 1687 1798 815 35 401 1014 117 1801 ...

result:

ok AC

Test #16:

score: 0
Accepted
time: 94ms
memory: 19448kb

input:

6993 7000
6927 2941
6385 1428
6914 2553
2474 4268
2068 1640
2298 6960
6201 1806
4912 59
4407 5504
1595 6868
6378 2515
3713 3724
2995 2589
2314 2932
4042 431
6322 4178
5947 6850
6192 735
3802 1043
4982 1575
311 6496
5006 3191
6473 3084
2387 4706
6632 5901
5113 3066
5248 1274
5671 717
1311 4261
1960 3...

output:

1062 718 9 1507 1103 1777 1477 1778 1088 10 11 382 911 15 16 20 465 21 962 807 22 23 1787 1466 738 788 546 799 1669 554 24 25 1790 495 26 27 1643 1532 28 799 31 32 1089 230 37 917 763 1796 1797 1657 1798 981 36 237 1802 37 38 1763 1620 1803 1763 1100 196 1377 1804 700 596 39 40 1203 41 500 42 1806 5...

result:

ok AC

Test #17:

score: 0
Accepted
time: 93ms
memory: 19104kb

input:

6930 7000
3746 2945
3523 6758
4109 1106
2732 5415
2423 844
3702 6309
6503 5362
5997 6294
5688 1396
4842 1764
4780 4521
1254 826
37 4653
2138 2358
6345 1223
1385 2341
5261 5867
4815 2918
4209 696
4235 2314
3680 2919
5605 5155
6643 3391
2691 1418
6289 2093
1970 1804
828 5237
4025 1111
1164 5519
5889 2...

output:

1717 1 2 1539 1147 802 5 1721 1483 1722 429 312 1477 6 7 9 1724 860 1359 1412 636 10 1131 885 11 1725 1649 1726 795 12 1085 14 15 1642 1255 1135 1728 16 40 17 18 19 1586 1729 1730 1427 1731 1395 1638 1184 1503 1734 509 1735 25 26 27 1741 221 28 1742 29 111 1281 788 30 1133 818 667 1441 33 34 1743 35...

result:

ok AC

Test #18:

score: 0
Accepted
time: 71ms
memory: 16280kb

input:

6300 7000
5921 5466
723 5843
1084 3134
3865 5742
5492 2885
328 4408
6055 4074
3702 2240
1342 2353
295 734
553 48
4454 2980
1248 4460
5023 19
2784 441
105 844
6048 1773
4840 5260
3910 1292
5578 2864
4978 3116
6182 4962
2575 1661
5030 435
5861 4709
5033 358
1746 5816
5877 3921
2678 5679
1784 33
207 59...

output:

209 1 1363 2 915 3 4 17 1522 146 1523 1524 1525 1526 5 6 7 11 103 220 12 1529 1043 13 766 1530 641 14 153 1518 742 735 836 1531 1532 16 40 446 876 213 851 1328 1467 263 589 1533 1069 760 1534 681 1176 1180 1538 16 1171 20 21 966 988 23 1304 1517 1541 24 25 26 27 1297 412 10 674 28 1542 707 29 1369 1...

result:

ok AC

Test #19:

score: 0
Accepted
time: 5ms
memory: 6396kb

input:

2800 7000
218 2670
1436 2268
38 2781
55 783
549 1627
660 1609
2268 2645
1376 1395
2747 71
785 1451
1096 2633
2655 2557
1569 307
16 56
1993 2751
1154 2760
478 2452
1841 2764
155 1781
215 1432
1788 2548
193 2665
167 1038
2425 2314
439 1615
269 1187
1222 245
1638 2016
2352 1511
2333 1564
1667 2576
1751...

output:

1 230 230 230 14 230 230 2 230 230 230 230 230 230 230 230 230 230 3 230 230 230 230 26 230 230 230 230 230 230 79 4 230 230 230 217 230 230 230 230 230 230 230 230 119 230 230 230 230 5 230 39 230 230 230 230 230 230 230 230 230 6 230 7 230 230 27 160 64 230 230 230 8 230 230 9 230 230 230 230 230 ...

result:

ok AC

Test #20:

score: 0
Accepted
time: 98ms
memory: 19252kb

input:

7000 7000
4828 3840
4148 2678
1645 2954
5516 1204
4664 285
904 1978
1434 1688
1902 5205
1324 4512
1722 1246
6724 5227
524 196
937 6286
6609 4724
5408 5610
4405 2463
5493 1567
2625 2894
2378 3685
5399 6872
6475 6546
5697 1265
1811 1314
2347 3005
6245 271
2414 434
3492 6948
4447 599
793 6107
464 5353
...

output:

2168 1475 1400 2169 2170 411 2171 972 1 2172 156 68 1076 2 3 1874 1687 348 2174 775 677 2175 1674 4 977 977 903 2176 2177 5 766 700 2179 1277 1988 6 2180 1364 7 215 2181 1252 8 9 396 2183 10 1637 2184 1075 2185 2186 2187 355 2188 2189 213 2190 1615 11 2191 12 214 127 2192 13 2194 1395 14 707 2197 21...

result:

ok AC

Test #21:

score: 0
Accepted
time: 92ms
memory: 19248kb

input:

6993 7000
1576 5558
2853 3183
212 2572
1001 75
3386 6483
401 22
489 6768
6520 1684
6439 6188
3810 6414
4088 1924
371 1666
2822 410
5664 1676
1043 1365
384 2688
4179 6357
6466 4630
2829 4371
116 6817
1535 6172
751 5740
499 2484
2013 4576
6556 670
6177 3847
5344 4280
6103 1055
496 4934
6639 217
6606 4...

output:

1587 2 3 636 2181 580 360 1070 4 5 6 2182 2183 2184 1280 1777 908 2185 2163 1110 7 952 423 542 1436 1156 2186 2124 2187 9 10 2188 11 2189 12 2190 374 2191 525 2192 1097 1841 13 14 1109 2193 15 16 730 1324 2196 281 2115 2197 2198 2199 1814 906 310 2200 2201 19 20 1981 1158 21 139 22 1607 1879 2203 22...

result:

ok AC

Test #22:

score: 0
Accepted
time: 92ms
memory: 21292kb

input:

6930 7000
2378 5636
2953 3870
897 2126
112 1756
3302 5114
4591 5593
5408 4899
1204 6313
6254 2214
5360 6680
2354 5865
5959 5969
1628 5317
6396 1006
2402 1767
1921 3373
3758 312
2167 5711
4119 6585
19 3951
1714 1206
3754 4376
4516 307
6312 165
5721 2470
4828 4842
4520 4310
1922 4946
2006 3856
1218 58...

output:

2137 2150 2151 1 2152 314 2 2061 2153 3 2154 4 1636 5 6 7 9 1050 10 11 1493 1932 2157 265 2159 405 1496 1790 2160 12 13 14 1803 992 15 1021 2162 1769 2163 2164 17 2165 18 2166 1011 19 20 22 2169 2170 2092 1601 2171 23 2172 2173 2174 24 2175 2176 1569 452 2177 2178 2179 1458 2180 880 26 27 50 2182 21...

result:

ok AC

Test #23:

score: 0
Accepted
time: 68ms
memory: 17420kb

input:

6300 7000
1562 45
1716 2699
5291 4828
5063 4588
5888 4130
5901 6109
1476 921
3390 5892
5425 3782
824 5679
2278 6102
6146 5556
4874 2115
2842 2803
1963 5131
3736 2611
320 5272
758 5667
4087 228
5139 760
1812 2968
2897 6117
277 387
336 1322
4319 4597
608 4481
6182 3050
4333 3570
401 1662
3085 3197
537...

output:

1993 1 719 1033 1994 1215 1995 1996 41 1997 1380 1998 2 1066 815 3 982 878 1532 2003 2004 2005 4 5 589 2006 1159 7 1219 1236 2008 8 10 12 1287 810 13 14 1089 549 16 448 17 2012 18 816 2014 19 2015 1913 2016 2017 938 20 29 2019 2020 21 1043 2021 2022 231 93 22 1069 1165 23 24 368 2026 26 2028 2029 27...

result:

ok AC

Test #24:

score: 0
Accepted
time: 21ms
memory: 12868kb

input:

2800 7000
931 1154
1783 1159
2515 1596
1734 1277
825 430
938 208
288 684
970 2075
618 2411
2690 500
223 2162
2093 2765
172 1029
832 1571
89 2333
2301 981
1354 1094
1989 137
2340 1804
2600 1249
1714 2343
1043 2738
1375 1239
804 2578
424 1572
568 1945
2233 297
1890 519
1475 944
2732 1123
2012 927
2232...

output:

388 2 270 4 5 6 332 7 385 8 172 703 737 387 9 510 117 731 10 134 11 245 311 16 722 19 595 63 771 218 17 18 399 19 24 25 26 148 396 27 772 36 4 286 28 655 32 33 34 698 774 35 36 116 37 775 25 367 38 39 528 41 204 33 389 42 44 230 704 696 745 304 161 52 53 536 54 165 55 435 204 57 295 58 665 58 432 50...

result:

ok AC

Test #25:

score: 0
Accepted
time: 3ms
memory: 6096kb

input:

52 41
18 31
2 5
22 32
1 50
50 29
9 32
44 27
45 17
26 24
18 30
28 25
38 28
5 47
49 38
23 50
8 3
16 24
29 46
7 52
30 38
33 32
39 32
3 18
50 44
1 35
49 37
18 24
29 6
20 39
40 45
33 28
51 52
26 40
38 43
52 45
39 40
42 34
6 45
32 19
20 52
34 28

output:

2 3 4 15 3 1 16 4 17 18 19 20 21 22 23 5 8 4 9 6 24 25 7 5 10 8 7 10 1 4 14 9 9 10 2 26 11 4 6 8 27 10 4 7 8 13 3 28 11 7 12 12 

result:

ok AC

Test #26:

score: 0
Accepted
time: 3ms
memory: 7780kb

input:

291 56
117 283
21 277
128 22
245 45
8 223
150 129
16 15
224 163
288 76
218 238
25 233
100 262
244 101
76 207
286 80
164 238
165 283
133 251
23 235
22 280
65 205
8 30
66 76
232 90
251 287
80 62
58 218
285 225
247 199
149 34
219 16
286 221
174 248
20 58
169 69
229 119
178 216
152 147
148 189
116 207
7...

output:

38 7 39 40 41 42 43 1 45 46 47 48 49 50 28 28 51 52 53 2 12 16 3 54 4 55 56 57 58 1 59 60 5 61 62 63 64 65 66 6 67 68 69 70 32 71 72 73 74 7 75 76 77 78 79 80 81 2 82 83 84 11 85 86 8 87 88 89 23 90 91 9 10 93 94 37 95 96 97 11 98 99 100 101 102 103 12 104 105 30 106 107 108 109 110 111 92 112 113 1...

result:

ok AC

Test #27:

score: 0
Accepted
time: 1ms
memory: 8024kb

input:

26 295
19 5
19 13
10 2
14 13
19 24
20 13
9 3
18 11
13 25
13 14
24 6
1 2
25 6
6 13
7 25
1 9
2 8
6 8
13 18
2 7
11 9
14 12
21 19
17 23
8 14
3 5
22 8
8 3
25 5
24 21
10 3
23 13
24 20
3 21
23 18
7 15
24 18
18 21
18 4
8 12
13 9
12 1
14 9
18 20
9 22
10 25
3 26
2 14
5 20
1 24
24 1
23 6
18 6
21 11
19 4
24 25
...

output:

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 

result:

ok AC

Test #28:

score: 0
Accepted
time: 2ms
memory: 5652kb

input:

63 1000
22 9
25 11
52 54
34 30
18 8
24 3
42 30
61 51
34 17
36 52
58 9
41 53
19 12
40 3
54 47
23 51
44 59
10 21
35 52
34 56
43 15
39 41
12 37
13 21
55 48
16 57
39 25
26 25
22 57
54 34
63 55
11 27
60 40
41 1
24 59
20 53
14 6
51 35
44 9
47 35
32 39
40 28
9 49
29 27
16 25
56 53
28 56
5 39
35 57
61 37
22...

output:

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 

result:

ok AC

Test #29:

score: 0
Accepted
time: 3ms
memory: 6100kb

input:

42 113
29 15
21 15
28 13
30 42
7 33
4 31
16 18
11 36
38 13
33 6
28 27
17 19
21 25
42 4
19 16
8 37
38 4
4 19
20 22
33 27
26 42
31 39
14 29
6 32
20 12
40 6
32 28
23 18
41 22
10 4
7 28
31 13
14 24
37 40
9 20
26 32
13 18
35 29
9 29
34 26
19 32
20 25
34 39
33 23
28 35
35 22
7 16
40 13
39 24
24 20
18 24
4...

output:

1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 

result:

ok AC

Test #30:

score: 0
Accepted
time: 2ms
memory: 5884kb

input:

6 8
5 1
1 5
6 5
4 1
4 3
2 4
5 3
3 4

output:

1 2 1 1 1 1 

result:

ok AC

Test #31:

score: 0
Accepted
time: 81ms
memory: 14800kb

input:

7000 6999
6253 1991
6253 4600
1137 6253
1764 6253
6253 908
6253 2205
6253 213
6253 4399
6300 6253
4601 6253
6253 4884
6937 6253
6253 4070
2646 6253
1007 6253
6552 6253
6253 2115
6253 922
6223 6253
6253 2496
3522 6253
2050 6253
6253 763
6803 6253
6253 3847
2816 6253
6253 6297
6253 471
6253 3211
3203 ...

output:

3483 3484 2451 3258 3485 1798 3486 80 1762 3487 3488 2923 1320 3181 3489 360 3490 3491 2861 3492 3493 142 3161 3494 3495 2231 3496 1069 57 2578 1152 1030 3497 3498 3499 2398 3500 404 347 569 886 3501 2139 3502 869 3503 720 3504 3505 3506 687 2419 3507 3508 3509 131 1344 2177 1149 2003 3510 606 930 3...

result:

ok AC