F1. Animal Observation (easy version)

time_limit: 3 seconds

memory_limit: 512 megabytes

note:
The optimal way to observe animals in the four examples are as follows:
Example 1:
![image](images/cf_1304_F1/1.png)
Example 2:
![image](images/cf_1304_F1/2.png)
Example 3:
![image](images/cf_1304_F1/3.png)
Example 4:
![image](images/cf_1304_F1/4.png)

solutions: ["import sys, os, io\r\ninput = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline\r\n\r\ndef sparse_table(a):\r\n    table = []\r\n    s0, l = a, 1\r\n    table.append(s0)\r\n    while 2 * l <= len(a):\r\n        s = [max(s0[i], s0[i + l]) for i in range(len(s0) - l)]\r\n        table.append(list(s))\r\n        s0 = s\r\n        l *= 2\r\n    return table\r\n\r\ndef get_max(l, r, table):\r\n    d = len(bin(r - l + 1)) - 3\r\n    ans = max(table[d][l], table[d][r - pow2[d] + 1])\r\n    return ans\r\n\r\nn, m, k = map(int, input().split())\r\ns = []\r\nfor _ in range(n):\r\n    s0 = list(map(int, input().split()))\r\n    u = [0]\r\n    for i in s0:\r\n        u.append(u[-1] + i)\r\n    s.append(u)\r\ns.append([0] * (m + 1))\r\nl = m - k + 1\r\ndp0 = [0] * l\r\ns0, s1 = s[0], s[1]\r\nfor i in range(l):\r\n    dp0[i] = s0[i + k] + s1[i + k] - s0[i] - s1[i]\r\ns0 = s[1]\r\npow2 = [1]\r\nfor _ in range(20):\r\n    pow2.append(2 * pow2[-1])\r\nfor i in range(1, n):\r\n    s1 = s[i + 1]\r\n    dp = [0] * l\r\n    table = sparse_table(dp0)\r\n    for j in range(l):\r\n        c = s0[j + k] + s1[j + k] - s0[j] - s1[j]\r\n        dpj = 0\r\n        for u in range(max(0, j - k + 1), min(l, j + k)):\r\n            x, y = max(j, u), min(j, u) + k\r\n            dpj = max(dpj, dp0[u] + c - s0[y] + s0[x])\r\n        if j - k >= 0:\r\n            dpj = max(dpj, get_max(0, j - k, table) + c)\r\n        if j + k <= l - 1:\r\n            dpj = max(dpj, get_max(j + k, l - 1, table) + c)\r\n        dp[j] = dpj\r\n    dp0 = dp\r\n    s0 = s1\r\nans = max(dp0)\r\nprint(ans)"]

source: codeforces

raw_problem:
F1. Animal Observation (easy version)

time limit per test
3 seconds

memory limit per test
512 megabytes

input
standard input

output
standard output

The only difference between easy and hard versions is the constraint on $$$k$$$.

Gildong loves observing animals, so he bought two cameras to take videos of wild animals in a forest. The color of one camera is red, and the other one's color is blue.

Gildong is going to take videos for $$$n$$$ days, starting from day $$$1$$$ to day $$$n$$$. The forest can be divided into $$$m$$$ areas, numbered from $$$1$$$ to $$$m$$$. He'll use the cameras in the following way:

 On every odd day ($$$1$$$-st, $$$3$$$-rd, $$$5$$$-th, ...), bring the red camera to the forest and record a video for $$$2$$$ days.

 On every even day ($$$2$$$-nd, $$$4$$$-th, $$$6$$$-th, ...), bring the blue camera to the forest and record a video for $$$2$$$ days.

 If he starts recording on the $$$n$$$-th day with one of the cameras, the camera records for only one day.

Each camera can observe $$$k$$$ consecutive areas of the forest. For example, if $$$m=5$$$ and $$$k=3$$$, he can put a camera to observe one of these three ranges of areas for two days: $$$[1,3]$$$, $$$[2,4]$$$, and $$$[3,5]$$$.

Gildong got information about how many animals will be seen in each area each day. Since he would like to observe as many animals as possible, he wants you to find the best way to place the two cameras for $$$n$$$ days. Note that if the two cameras are observing the same area on the same day, the animals observed in that area are counted only once.

Input

The first line contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \le n \le 50$$$, $$$1 \le m \le 2 \cdot 10^4$$$, $$$1 \le k \le min(m,20)$$$) – the number of days Gildong is going to record, the number of areas of the forest, and the range of the cameras, respectively.

Next $$$n$$$ lines contain $$$m$$$ integers each. The $$$j$$$-th integer in the $$$i+1$$$-st line is the number of animals that can be seen on the $$$i$$$-th day in the $$$j$$$-th area. Each number of animals is between $$$0$$$ and $$$1000$$$, inclusive.

Output

Print one integer – the maximum number of animals that can be observed.

Examples

Input

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

Output

25

Input

3 3 1
1 2 3
4 5 6
7 8 9

Output

31

Input

3 3 2
1 2 3
4 5 6
7 8 9

Output

44

Input

3 3 3
1 2 3
4 5 6
7 8 9

Output

45

Note

The optimal way to observe animals in the four examples are as follows:

Example 1:

Example 2:

Example 3:

Example 4:

question:
The only difference between easy and hard versions is the constraint on $$$k$$$.
Gildong loves observing animals, so he bought two cameras to take videos of wild animals in a forest. The color of one camera is red, and the other one's color is blue.
Gildong is going to take videos for $$$n$$$ days, starting from day $$$1$$$ to day $$$n$$$. The forest can be divided into $$$m$$$ areas, numbered from $$$1$$$ to $$$m$$$. He'll use the cameras in the following way:
 -  On every odd day ($$$1$$$-st, $$$3$$$-rd, $$$5$$$-th, ...), bring the red camera to the forest and record a video for $$$2$$$ days. -  On every even day ($$$2$$$-nd, $$$4$$$-th, $$$6$$$-th, ...), bring the blue camera to the forest and record a video for $$$2$$$ days. -  If he starts recording on the $$$n$$$-th day with one of the cameras, the camera records for only one day. Each camera can observe $$$k$$$ consecutive areas of the forest. For example, if $$$m=5$$$ and $$$k=3$$$, he can put a camera to observe one of these three ranges of areas for two days: $$$[1,3]$$$, $$$[2,4]$$$, and $$$[3,5]$$$.
Gildong got information about how many animals will be seen in each area each day. Since he would like to observe as many animals as possible, he wants you to find the best way to place the two cameras for $$$n$$$ days. Note that if the two cameras are observing the same area on the same day, the animals observed in that area are counted only once.

Input
The first line contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \le n \le 50$$$, $$$1 \le m \le 2 \cdot 10^4$$$, $$$1 \le k \le min(m,20)$$$) – the number of days Gildong is going to record, the number of areas of the forest, and the range of the cameras, respectively.
Next $$$n$$$ lines contain $$$m$$$ integers each. The $$$j$$$-th integer in the $$$i+1$$$-st line is the number of animals that can be seen on the $$$i$$$-th day in the $$$j$$$-th area. Each number of animals is between $$$0$$$ and $$$1000$$$, inclusive.

Output
Print one integer – the maximum number of animals that can be observed.

Examples
Input
4 5 2
0 2 1 1 0
0 0 3 1 2
1 0 4 3 1
3 3 0 0 4

Output
25

Input
3 3 1
1 2 3
4 5 6
7 8 9

Output
31

Input
3 3 2
1 2 3
4 5 6
7 8 9

Output
44

Input
3 3 3
1 2 3
4 5 6
7 8 9

Output
45

Note
The optimal way to observe animals in the four examples are as follows:
Example 1:
 ![image](1.png) Example 2:
 ![image](2.png) Example 3:
 ![image](3.png) Example 4:
 ![image](4.png)

image_tags: Patterns Patterns Patterns Patterns

data_split: test


B. Maximum Xor Secondary

problem_index: B

time_limit: 1 second

memory_limit: 256 megabytes

solutions: ["import sys\ninput = sys.stdin.readline\nn = int(input())\na = list(map(int, input().split()))\nans = 0\nd = []\nfor i in a:\n\twhile len(d) and d[-1] < i:\n\t\tans = max(ans, d[-1] ^ i)\n\t\td.pop()\n\tif len(d):\n\t\tans = max(ans, d[-1] ^ i)\n\td.append(i)\nd = []\nprint(ans)\n", "n = int(input())\nl = [int(i) for i in input().split()]\nans = 0\nstack = []\nfor i in range(n):\n\twhile len(stack) != 0:\n\t\tif l[i] > stack[len(stack) - 1]:\n\t\t\tans = max(ans, l[i] ^ stack[len(stack) - 1])\n\t\t\tstack.pop()\n\t\telse:\n\t\t\tans = max(ans, l[i] ^ stack[len(stack) - 1])\n\t\t\tbreak\n\tstack.append(l[i])\nprint(ans)\n", "from collections import deque\n\ndef ngr(a, n):\n\ts = deque()\n\tl = []\n\tfor j in range(n - 1, -1, -1):\n\t\tif len(s) == 0:\n\t\t\ts.append(a[j])\n\t\t\tl.append(-1)\n\t\telse:\n\t\t\twhile len(s) != 0 and s[len(s) - 1] <= a[j]:\n\t\t\t\ts.pop()\n\t\t\tif len(s) == 0:\n\t\t\t\tl.append(-1)\n\t\t\telse:\n\t\t\t\tl.append(s[len(s) - 1] ^ a[j])\n\t\t\ts.append(a[j])\n\tl.reverse()\n\treturn l\n\ndef ngl(a, n):\n\ts = deque()\n\tl = []\n\tfor j in range(n):\n\t\tif len(s) == 0:\n\t\t\ts.append(a[j])\n\t\t\tl.append(-1)\n\t\telse:\n\t\t\twhile len(s) != 0 and s[len(s) - 1] <= a[j]:\n\t\t\t\ts.pop()\n\t\t\tif len(s) == 0:\n\t\t\t\tl.append(-1)\n\t\t\telse:\n\t\t\t\tl.append(s[len(s) - 1] ^ a[j])\n\t\t\ts.append(a[j])\n\treturn l\nn = int(input())\na = list(map(int, input().split()))\nc = ngr(a, n)\nd = ngl(a, n)\nc.extend(d)\nprint(max(c))\n", "n = int(input())\na = list(map(int, input().strip().split()))\nstack = []\nmax_xor = 0\nfor k in range(n):\n\tif not stack:\n\t\tstack.append(a[k])\n\telif a[k] < stack[-1]:\n\t\tmax_xor = max(max_xor, a[k] ^ stack[-1])\n\t\tstack.append(a[k])\n\telif a[k] > stack[-1]:\n\t\twhile stack and a[k] > stack[-1]:\n\t\t\tpopped = stack.pop()\n\t\t\tmax_xor = max(max_xor, a[k] ^ popped)\n\t\tif stack:\n\t\t\tmax_xor = max(max_xor, a[k] ^ stack[-1])\n\t\tstack.append(a[k])\nprint(max_xor)\n", "n = int(input())\nnl = [int(x) for x in input().split()]\nst = []\nans = 0\nfor x in nl:\n\tif st and st[-1] > x:\n\t\tans = max(ans, st[-1] ^ x)\n\telif st:\n\t\twhile st and st[-1] < x:\n\t\t\tans = max(ans, st.pop() ^ x)\n\t\tif st:\n\t\t\tans = max(ans, st[-1] ^ x)\n\tst.append(x)\nprint(ans)\n", "import sys\ninp = sys.stdin.readlines()\nn = int(inp[0])\narr = list(map(int, inp[1].split()))\nmaxglobal = -1\ntop = -1\nstack = [0] * n\nfor i in range(n):\n\twhile top != -1:\n\t\tmaxglobal = max(maxglobal, stack[top] ^ arr[i])\n\t\tif stack[top] < arr[i]:\n\t\t\ttop -= 1\n\t\telse:\n\t\t\tbreak\n\tstack[top + 1] = arr[i]\n\ttop += 1\nprint(maxglobal)\n", "m = int(input())\nl = list(map(int, input().split()))\nmax_lucky = 0\nstack = []\nfor i in range(m):\n\twhile stack:\n\t\tif stack[-1] < l[i]:\n\t\t\tmax_lucky = max(stack[-1] ^ l[i], max_lucky)\n\t\t\tstack.pop()\n\t\telse:\n\t\t\tmax_lucky = max(stack[-1] ^ l[i], max_lucky)\n\t\t\tbreak\n\tstack.append(l[i])\nprint(max_lucky)\n", "n = int(input())\narr = list(map(int, input().split()))\ns = []\nans = 0\nfor i in arr:\n\twhile s:\n\t\tans = max(ans, s[-1] ^ i)\n\t\tif s[-1] > i:\n\t\t\tbreak\n\t\telse:\n\t\t\ts.pop()\n\ts.append(i)\nprint(ans)\n", "def xor(a, b):\n\treturn a ^ b\n\ndef solve(l):\n\tans = xor(l[0], l[1])\n\tst = [l[0], l[1]]\n\tfor i in range(2, n):\n\t\twhile len(st) > 0 and st[-1] < l[i]:\n\t\t\tst.pop()\n\t\tst.append(l[i])\n\t\tif len(st) >= 2:\n\t\t\tans = max(ans, xor(st[-1], st[-2]))\n\treturn ans\nn = int(input())\nl = input()\nl = [int(i) for i in l.split()]\nans = solve(l)\nl.reverse()\nans = max(ans, solve(l))\nprint(ans)\n", "from math import *\nimport functools\ninput()\nnumbs = [int(s) for s in input().split()]\n\ndef getMaxPot2(x):\n\tres = 1\n\twhile 2 * res <= x:\n\t\tres *= 2\n\treturn res\na = functools.reduce(lambda x, y: x & y, numbs)\nnumbs = [a ^ s for s in numbs]\nmaxPot2 = getMaxPot2(max(numbs))\nres = 0\nfor (i, val) in enumerate(numbs):\n\tif val & maxPot2 > 0:\n\t\t(max2, j) = (-1, i - 1)\n\t\twhile j >= 0 and numbs[j] & maxPot2 == 0:\n\t\t\tif numbs[j] > max2:\n\t\t\t\tmax2 = numbs[j]\n\t\t\t\tres = max(res, val ^ max2)\n\t\t\tj -= 1\n\t\t(max2, j) = (-1, i + 1)\n\t\twhile j < len(numbs) and numbs[j] & maxPot2 == 0:\n\t\t\tif numbs[j] > max2:\n\t\t\t\tmax2 = numbs[j]\n\t\t\t\tres = max(res, val ^ max2)\n\t\t\tj += 1\nprint(res)\n", "n = input()\nnos = [int(x) for x in input().split()]\n(stack, ans) = ([], 0)\nfor n in nos:\n\twhile stack:\n\t\tans = max(ans, stack[-1] ^ n)\n\t\tif stack[-1] > n:\n\t\t\tbreak\n\t\telse:\n\t\t\tstack.pop()\n\tstack.append(n)\nprint(ans)\n", "def f(a):\n\tstack = []\n\tans = -1\n\tfor i in range(0, len(a)):\n\t\twhile stack and a[i] >= stack[-1]:\n\t\t\tans = max(ans, a[i] ^ stack[-1])\n\t\t\tstack.pop(-1)\n\t\tstack.append(a[i])\n\treturn ans\na = map(int, input().strip().split())\nl = list(map(int, input().strip().split()))\nan = -1\nan = max(f(l), f(l[::-1]))\nprint(an)\n", "def maximum_xor_secondary(sequence):\n\t(stack, answer) = ([], 0)\n\tfor x in sequence:\n\t\twhile stack:\n\t\t\tanswer = max(answer, stack[-1] ^ x)\n\t\t\tif stack[-1] > x:\n\t\t\t\tbreak\n\t\t\telse:\n\t\t\t\tstack.pop()\n\t\tstack.append(x)\n\treturn answer\n(size, num) = (input(), [int(x) for x in input().split()])\nprint(maximum_xor_secondary(num))\n", "n = int(input())\narr = list(map(int, input().strip().split(' ')))\nres = 0\nst = []\nfor i in range(n):\n\twhile st:\n\t\tres = max(res, arr[st[-1]] ^ arr[i])\n\t\tif arr[i] > arr[st[-1]]:\n\t\t\tst.pop(-1)\n\t\telse:\n\t\t\tbreak\n\tst.append(i)\nprint(res)\n", "n = int(input())\nnlist = list(map(int, input().split()))\nstack = list()\nresult = 0\nfor i in range(n):\n\twhile stack != []:\n\t\tresult = max(result, stack[-1] ^ nlist[i])\n\t\tif stack[-1] > nlist[i]:\n\t\t\tbreak\n\t\telse:\n\t\t\tstack.pop()\n\tstack.append(nlist[i])\nprint(result)\n", "n = int(input())\nl = [int(e) for e in input().split()]\ns = [l[0]]\nm = 0\nfor i in range(1, n):\n\tif l[i] < s[-1]:\n\t\tm = max(m, l[i] ^ s[-1])\n\telse:\n\t\twhile len(s) != 0 and l[i] > s[-1]:\n\t\t\tx = s.pop()\n\t\t\tm = max(m, l[i] ^ x)\n\t\tif len(s) != 0:\n\t\t\tm = max(m, l[i] ^ s[-1])\n\ts.append(l[i])\nprint(m)\n", "import sys\nn = int(input())\na = list(map(int, input().split()))\nb = [a[0]]\nm = 0\nfor i in range(1, n):\n\tif len(b) > 0:\n\t\tm = max(m, b[-1] ^ a[i])\n\twhile len(b) > 0 and a[i] > b[-1]:\n\t\tm = max(m, b[-1] ^ a[i])\n\t\tb.pop()\n\tif len(b) > 0:\n\t\tm = max(m, b[-1] ^ a[i])\n\tb.append(a[i])\nprint(m)\n", "import sys\n\ndef input():\n\treturn sys.stdin.readline().strip()\nStack = []\nN = int(input())\nA = list(map(int, input().split(' ')))\nAns = 0\nfor i in A:\n\twhile len(Stack) != 0:\n\t\tif i > Stack[-1]:\n\t\t\tAns = max(Ans, i ^ Stack[-1])\n\t\t\tStack.pop()\n\t\telse:\n\t\t\tAns = max(Ans, Stack[-1] ^ i)\n\t\t\tbreak\n\tStack.append(i)\nprint(Ans)\n", "n = int(input())\na = list(map(int, input().split()))\nst = a[:2]\nmx = a[0] ^ a[1]\nfor i in a[2:]:\n\twhile st and st[-1] < i:\n\t\tst.pop()\n\tst.append(i)\n\tl = st.pop()\n\tif st:\n\t\tmx = max(mx, st[-1] ^ l)\n\tst.append(l)\nst = a[:n - 3:-1]\nmx = max(mx, a[n - 1] ^ a[n - 2])\nfor i in a[n - 3::-1]:\n\twhile st and st[-1] < i:\n\t\tst.pop()\n\tst.append(i)\n\tl = st.pop()\n\tif st:\n\t\tmx = max(mx, st[-1] ^ l)\n\tst.append(l)\nprint(mx)\n", "from sys import stdin\nip = stdin.readline\nn = int(ip())\na = list(map(int, ip().split()))\nstk = [a[0]]\nans = 0\nfor i in range(1, n):\n\tval = a[i]\n\tans = max(ans, val ^ a[i - 1])\n\twhile stk and stk[-1] < val:\n\t\tans = max(ans, val ^ stk.pop())\n\tif stk:\n\t\tans = max(ans, stk[-1] ^ val)\n\tstk.append(val)\nprint(ans)\n", "n = int(input())\nli_t = list(map(int, input().split()))\nstk1 = []\nans = 0\nfor i in li_t:\n\twhile stk1 != []:\n\t\tif stk1[-1] < i:\n\t\t\tans = max(ans, stk1[-1] ^ i)\n\t\t\tstk1.pop()\n\t\telse:\n\t\t\tans = max(ans, stk1[-1] ^ i)\n\t\t\tbreak\n\tstk1.append(i)\nprint(ans)\n", "n = int(input())\na = [int(i) for i in input().split()]\nst = []\nans = 0\nfor i in a:\n\twhile st:\n\t\tif st[-1] < i:\n\t\t\tans = max(ans, st[-1] ^ i)\n\t\t\tst.pop()\n\t\telse:\n\t\t\tans = max(ans, st[-1] ^ i)\n\t\t\tbreak\n\tst.append(i)\nprint(ans)\n", "n = int(input())\nsn = list(map(int, input().split()))\nans = 0\nstack = []\nfor i in range(n):\n\twhile len(stack) and sn[i] > sn[stack[-1]]:\n\t\tl = stack.pop()\n\t\tans = max(ans, sn[l] ^ sn[i])\n\tif len(stack):\n\t\tans = max(ans, sn[i] ^ sn[stack[-1]])\n\tstack.append(i)\nprint(ans)\n", "from sys import stdin\nip = stdin.readline\nip()\na = list(map(int, ip().split()))\nstk = []\nans = 0\nfor i in a:\n\twhile stk:\n\t\tans = max(ans, stk[-1] ^ i)\n\t\tif stk[-1] > i:\n\t\t\tbreak\n\t\tstk.pop()\n\tstk.append(i)\nprint(ans)\n", "x = input()\nl = list(map(int, input().split()))\nans = 0\nd = []\nfor i in l:\n\twhile d != []:\n\t\tif d[-1] < i:\n\t\t\tans = max(ans, d[-1] ^ i)\n\t\t\td.pop()\n\t\telse:\n\t\t\tans = max(ans, d[-1] ^ i)\n\t\t\tbreak\n\td.append(i)\nprint(ans)\n", "def get_max_xor(num_list):\n\tstack = []\n\tmax_xor = num_list[0] ^ num_list[1]\n\tfor i in range(len(num_list)):\n\t\twhile stack and stack[-1] < num_list[i]:\n\t\t\tstack.pop()\n\t\tstack.append(num_list[i])\n\t\tif len(stack) > 1:\n\t\t\tmax_xor = max(max_xor, stack[-1] ^ stack[-2])\n\treturn max_xor\nlist_len = int(input())\nnum_list = list(map(int, input().split()))\nprint(max(get_max_xor(num_list), get_max_xor(num_list[::-1])))\n", "def empty(l):\n\treturn len(l) == 0\n\ndef lucky_number(arr):\n\tst = []\n\tl = 0\n\tfor d in arr:\n\t\twhile not empty(st) and st[-1] < d:\n\t\t\tl = max(l, st.pop() ^ d)\n\t\tif not empty(st):\n\t\t\tl = max(l, st[-1] ^ d)\n\t\tst.append(d)\n\td = 0\n\tif not empty(st):\n\t\td = st.pop()\n\twhile not empty(st):\n\t\tl = max(l, d ^ st[-1])\n\t\td = st.pop()\n\treturn l\nN = int(input())\narr = list(map(int, input().split()))\nprint(lucky_number(arr))\n", "n = int(input())\ns = list(map(int, input().split()))\nstack = []\nans = 0\nfor i in s:\n\twhile stack and stack[-1] < i:\n\t\tt = stack.pop()\n\t\tans = max(ans, t ^ i)\n\tstack.append(i)\n\tif stack[0] != stack[-1]:\n\t\tans = max(ans, stack[-1] ^ stack[-2])\nprint(ans)\n", "n = int(input())\n[first_value, *sn] = list(map(int, input().strip().split()))\nans = 0\nstack = [None] * n\ntop = 0\nstack[top] = first_value\nfor s in sn:\n\tif s > stack[top]:\n\t\twhile top > -1 and s > stack[top]:\n\t\t\tans = max(ans, s ^ stack[top])\n\t\t\ttop -= 1\n\t\tif top > -1:\n\t\t\tans = max(ans, s ^ stack[top])\n\t\ttop += 1\n\t\tstack[top] = s\n\telse:\n\t\tans = max(ans, s ^ stack[top])\n\t\ttop += 1\n\t\tstack[top] = s\nprint(ans)\n", "def fun(numbers):\n\tle = len(numbers)\n\tstack = []\n\tans = 0\n\ti = 1\n\tfor i in numbers:\n\t\twhile stack:\n\t\t\tans = max(ans, stack[-1] ^ i)\n\t\t\tif stack[-1] > i:\n\t\t\t\tbreak\n\t\t\telse:\n\t\t\t\tstack.pop()\n\t\tstack.append(i)\n\treturn ans\nn = input()\nuser_input = input().split(' ')\nnumbers = [int(x.strip()) for x in user_input]\nprint(fun(numbers))\n", "n = int(input())\nli = [int(x) for x in input().split()]\nstack = []\nlarge = 0\nfor i in range(0, n):\n\twhile len(stack) != 0:\n\t\tif stack[-1] < li[i]:\n\t\t\tlarge = max(large, stack[-1] ^ li[i])\n\t\t\tstack.pop()\n\t\telse:\n\t\t\tlarge = max(large, stack[-1] ^ li[i])\n\t\t\tbreak\n\tstack.append(li[i])\nprint(large)\n", "num = int(input())\narr = [int(i) for i in input().split()]\nans = 0\nstack = [arr[0]]\nfor i in arr:\n\twhile stack:\n\t\tans = max(ans, stack[-1] ^ i)\n\t\tif stack[-1] > i:\n\t\t\tbreak\n\t\telse:\n\t\t\tstack.pop()\n\tstack.append(i)\nprint(ans)\n", "n = int(input())\nli = [int(x) for x in input().split()]\nmonD = []\nans = 0\nfor (i, j) in zip(li, range(0, len(li))):\n\tif j == 0:\n\t\tmonD.append(i)\n\telse:\n\t\tfl = 1\n\t\tif monD[-1] > i:\n\t\t\tans = max(ans, i ^ monD[-1])\n\t\t\tmonD.append(i)\n\t\telse:\n\t\t\twhile monD[-1] < i:\n\t\t\t\tans = max(ans, i ^ monD[-1])\n\t\t\t\t_ = monD.pop()\n\t\t\t\tif len(monD) == 0:\n\t\t\t\t\tfl = 0\n\t\t\t\t\tbreak\n\t\t\tif fl != 0:\n\t\t\t\tans = max(ans, i ^ monD[-1])\n\t\t\tmonD.append(i)\nprint(ans)\n", "size = int(input())\narray = list(map(int, input().split()))\nmystack = []\nscore = None\nmaxim = 0\nindex = 0\nwhile index < size:\n\tif not mystack or array[mystack[-1]] > array[index]:\n\t\tmystack.append(index)\n\t\tindex += 1\n\telse:\n\t\twhile mystack and array[mystack[-1]] < array[index]:\n\t\t\ttop = mystack.pop()\n\t\t\tscore = int(array[top] ^ array[index])\n\t\t\tmaxim = max(score, maxim)\n\t\tmystack.append(index)\n\t\tindex += 1\nmystack.clear()\nindex = size - 1\nwhile index >= 0:\n\tif not mystack or array[mystack[-1]] > array[index]:\n\t\tmystack.append(index)\n\t\tindex -= 1\n\telse:\n\t\twhile mystack and array[mystack[-1]] < array[index]:\n\t\t\ttop = mystack.pop()\n\t\t\tscore = int(array[top] ^ array[index])\n\t\t\tmaxim = max(score, maxim)\n\t\tmystack.append(index)\n\t\tindex -= 1\nprint(maxim)\n", "n = int(input())\na = list(map(int, input().split()))\ns = list()\nans = 0\ns.append(a[0])\nfor i in range(1, n):\n\twhile s and a[i] > s[-1]:\n\t\tans = max(ans, a[i] ^ s.pop())\n\tif s:\n\t\tans = max(ans, a[i] ^ s[-1])\n\ts.append(a[i])\nprint(ans)\n", "n = int(input())\na = list(map(int, input().split()))\nstack = []\nxor = 0\nfor i in range(n):\n\twhile stack != [] and stack[-1] < a[i]:\n\t\txor = max(xor, a[i] ^ stack[-1])\n\t\tstack.pop()\n\tif stack != []:\n\t\txor = max(xor, a[i] ^ stack[-1])\n\tstack.append(a[i])\nprint(xor)\n", "n = int(input().strip())\nsequence = [int(x) for x in input().strip().split()]\nstack = []\nmax_xor = 0\nfor bar in sequence:\n\twhile stack:\n\t\tmax_xor = max(max_xor, stack[-1] ^ bar)\n\t\tif stack[-1] < bar:\n\t\t\tstack.pop()\n\t\telse:\n\t\t\tbreak\n\tstack.append(bar)\nprint(max_xor)\n", "n = int(input())\na = list(map(int, input().split()))\nm = 0\nstack = []\nfor i in a:\n\twhile stack:\n\t\tm = max(m, stack[-1] ^ i)\n\t\tif stack[-1] > i:\n\t\t\tbreak\n\t\telse:\n\t\t\tstack.pop()\n\tstack.append(i)\nprint(m)\n", "from collections import deque\nstack = deque()\nn = int(input())\na = list(map(int, input().split()))\nres1 = 0\nl = 0\nfor i in a:\n\twhile stack and stack[-1] < i:\n\t\tstack.pop()\n\t\tl -= 1\n\tstack.append(i)\n\tl += 1\n\tif l > 1:\n\t\tres1 = max(res1, stack[-1] ^ stack[-2])\nstack.clear()\nl = 0\nres2 = 0\na.reverse()\nfor i in a:\n\twhile stack and stack[-1] < i:\n\t\tstack.pop()\n\t\tl -= 1\n\tstack.append(i)\n\tl += 1\n\tif l > 1:\n\t\tres2 = max(res2, stack[-1] ^ stack[-2])\nprint(max(res1, res2))\n", "n = int(input())\na = list(map(int, input().split()))\nans = -1\nstack = []\nfor i in range(n):\n\twhile stack != []:\n\t\tans = max(ans, stack[-1] ^ a[i])\n\t\tif a[i] > stack[-1]:\n\t\t\tstack.pop()\n\t\telse:\n\t\t\tbreak\n\tstack.append(a[i])\nprint(ans)\n", "RI = lambda : [int(x) for x in input().split()]\nrw = lambda : [input().strip()]\nn = int(input())\nl = RI()\nstack = []\nindex_stack = -1\nmaxo = 0\ni = 0\nwhile i < n:\n\tif index_stack == -1 or stack[index_stack] > l[i]:\n\t\tstack.append(l[i])\n\t\tindex_stack += 1\n\t\ti += 1\n\telse:\n\t\tmaxo = max(stack[index_stack] ^ l[i], maxo)\n\t\ttemp = stack[index_stack]\n\t\tstack.pop()\n\t\tindex_stack -= 1\n\t\tif len(stack) != 0:\n\t\t\tmaxo = max(temp ^ stack[index_stack], maxo)\nwhile len(stack) != 1:\n\ttemp = stack[index_stack]\n\tstack.pop()\n\tindex_stack -= 1\n\tmaxo = max(temp ^ stack[index_stack], maxo)\nprint(maxo)\n", "l = int(input())\narr = [int(i) for i in input().split()]\nstack = [arr[0]]\nmaxa = 0\nx = 0\nfor i in range(1, len(arr)):\n\twhile len(stack) != 0 and arr[i] > stack[-1]:\n\t\tx = arr[i] ^ stack[-1]\n\t\tmaxa = max(maxa, x)\n\t\tstack.pop()\n\tif len(stack) != 0:\n\t\tx = arr[i] ^ stack[-1]\n\t\tmaxa = max(maxa, x)\n\tstack.append(arr[i])\nprint(maxa)\n", "t = input()\na = list(map(int, input().split()))\nm = 0\nl = []\nfor i in range(0, len(a)):\n\tb = a[i]\n\tif len(l) == 0:\n\t\tl.append(b)\n\telif l[-1] > b:\n\t\tif l[-1] ^ b > m:\n\t\t\tm = l[-1] ^ b\n\t\tl.append(b)\n\telse:\n\t\twhile len(l) > 0 and l[-1] < b:\n\t\t\tif l[-1] ^ b > m:\n\t\t\t\tm = l[-1] ^ b\n\t\t\tdel l[-1]\n\t\tl.append(b)\n\t\tif len(l) > 1:\n\t\t\tif l[-1] ^ l[-2] > m:\n\t\t\t\tm = l[-1] ^ l[-2]\nprint(m)\n", "N = int(input())\nW = list(map(int, input().split()))\n\ndef func(W):\n\t(st, ans) = ([W[0]], 0)\n\tfor i in W[1:]:\n\t\twhile len(st) and st[-1] < i:\n\t\t\tst.pop()\n\t\tans = max(ans, st[-1] ^ i) if len(st) else ans\n\t\tst.append(i)\n\treturn ans\nprint(max(func(W), func(W[::-1])))\n", "from os import path\nimport sys\nfrom functools import cmp_to_key as ctk\nfrom collections import deque, defaultdict as dd\nfrom bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right\nfrom itertools import permutations\nfrom datetime import datetime\nfrom math import ceil, sqrt, log, gcd\n\ndef ii():\n\treturn int(input())\n\ndef si():\n\treturn input()\n\ndef mi():\n\treturn list(map(int, input().split()))\n\ndef li():\n\treturn list(mi())\nabc = 'abcdefghijklmnopqrstuvwxyz'\nabd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}\nmod = 1000000007\ninf = float('inf')\nvow = ['a', 'e', 'i', 'o', 'u']\n(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])\n\ndef bo(i):\n\treturn ord(i) - ord('a')\n\ndef solve():\n\tn = ii()\n\ta = li()\n\tb = []\n\tfor j in range(31, -1, -1):\n\t\tfor i in range(n):\n\t\t\tif a[i] >> j & 1:\n\t\t\t\tb.append(i)\n\t\tif len(b) < n and len(b) > 0:\n\t\t\tbreak\n\t\tb = []\n\tif len(b) == n or len(b) == 0:\n\t\tprint(0)\n\t\treturn\n\tans = 0\n\tx = 0\n\tfor j in range(len(b) - 1):\n\t\tmx = 0\n\t\tx1 = a[b[j]]\n\t\tfor i in range(b[j] - 1, x - 1, -1):\n\t\t\tmx = max(mx, a[i])\n\t\t\tans = max(ans, x1 ^ mx)\n\t\tmx = 0\n\t\tfor i in range(b[j] + 1, b[j + 1]):\n\t\t\tmx = max(mx, a[i])\n\t\t\tans = max(ans, x1 ^ mx)\n\t\tx = b[j] + 1\n\tmx = 0\n\tx1 = a[b[len(b) - 1]]\n\tfor i in range(b[len(b) - 1] - 1, x - 1, -1):\n\t\tmx = max(mx, a[i])\n\t\tans = max(ans, x1 ^ mx)\n\tmx = 0\n\tfor i in range(b[len(b) - 1] + 1, n):\n\t\tmx = max(mx, a[i])\n\t\tans = max(ans, x1 ^ mx)\n\tprint(ans)\n\ndef __starting_point():\n\tsolve()\n__starting_point()\n", "n = int(input())\na = [int(k) for k in input().split()]\nif len(a) == 1:\n\tprint(a[0])\nelse:\n\td = [a[0], a[1]]\n\tc = a[0] ^ a[1]\n\tfor i in range(n):\n\t\twhile len(d) > 0 and a[i] > d[-1]:\n\t\t\td.pop()\n\t\td.append(a[i])\n\t\tif len(d) > 1:\n\t\t\tc = max(c, d[-1] ^ d[-2])\n\td = [a[-1], a[-2]]\n\te = max(c, a[-1] ^ a[-2])\n\tfor i in range(n - 3, -1, -1):\n\t\twhile len(d) > 0 and a[i] > d[-1]:\n\t\t\td.pop()\n\t\td.append(a[i])\n\t\tif len(d) > 1:\n\t\t\te = max(e, d[-1] ^ d[-2])\n\tprint(e)\n", "n = int(input())\na = list(map(int, input().split()))\nl = []\ns = 0\nfor i in range(n):\n\twhile l != []:\n\t\tif a[i] >= l[-1]:\n\t\t\ts = max(s, a[i] ^ l[-1])\n\t\t\tl.pop()\n\t\telse:\n\t\t\ts = max(s, a[i] ^ l[-1])\n\t\t\tbreak\n\tl.append(a[i])\nprint(s)\n", "n = int(input())\nls = list(map(int, input().split()))\nst = list()\nMax = 0\nfor i in range(n):\n\twhile len(st) > 0:\n\t\ttemp = st[len(st) - 1]\n\t\tMax = max(Max, temp ^ ls[i])\n\t\tif temp > ls[i]:\n\t\t\tbreak\n\t\tst.pop()\n\tst.append(ls[i])\nprint(Max)\n", "n = int(input())\na = list(map(int, input().split()))\nans = 0\nd = []\nfor i in a:\n\twhile len(d) and d[-1] < i:\n\t\tans = max(ans, d[-1] ^ i)\n\t\td.pop()\n\tif len(d):\n\t\tans = max(ans, d[-1] ^ i)\n\td.append(i)\nd = []\nprint(ans)\n", "import sys, os\nfrom io import BytesIO, IOBase\nmod = 10 ** 9 + 7\nMod = 998244353\nINF = float('inf')\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ntc = 1\nfor test in range(1, tc + 1):\n\tn = int(input())\n\ta = list(map(int, input().split()))\n\tPrev = [i for i in range(n)]\n\tNext = [i for i in range(n)]\n\tstack = []\n\tfor i in range(n):\n\t\twhile stack and a[stack[-1]] <= a[i]:\n\t\t\tstack.pop()\n\t\tif stack:\n\t\t\tPrev[i] = stack[-1]\n\t\tstack.append(i)\n\tstack = []\n\tfor i in range(n - 1, -1, -1):\n\t\twhile stack and a[stack[-1]] <= a[i]:\n\t\t\tstack.pop()\n\t\tif stack:\n\t\t\tNext[i] = stack[-1]\n\t\tstack.append(i)\n\tans = 0\n\tfor i in range(n):\n\t\tans = max(ans, a[i] ^ a[Prev[i]])\n\t\tans = max(ans, a[i] ^ a[Next[i]])\n\tprint(ans)\n", "from sys import stdin\n(lines, line_index) = (stdin.readlines(), -1)\n\ndef get_line():\n\tglobal lines, line_index\n\tline_index += 1\n\treturn lines[line_index]\n\ndef main():\n\tn = int(get_line())\n\tseq = [int(x) for x in get_line().split()]\n\tstack = []\n\tans = 0\n\tfor val in seq:\n\t\twhile stack:\n\t\t\tif stack[-1] < val:\n\t\t\t\tans = max(ans, stack[-1] ^ val)\n\t\t\t\tstack.pop()\n\t\t\telse:\n\t\t\t\tans = max(ans, stack[-1] ^ val)\n\t\t\t\tbreak\n\t\tstack.append(val)\n\tprint(ans)\nmain()\n", "n = int(input())\na = [int(n) for n in input().split()]\nstack = []\nmaxx = 0\ni = 0\nwhile i < n:\n\tif not stack or a[i] < stack[-1]:\n\t\tstack.append(a[i])\n\t\ti += 1\n\telse:\n\t\tmaxx = max(stack[-1] ^ a[i], maxx)\n\t\ttemp = stack.pop()\n\t\tif stack:\n\t\t\tmaxx = max(stack[-1] ^ temp, maxx)\nwhile len(stack) != 1:\n\ttemp = stack.pop()\n\tmaxx = max(temp ^ stack[-1], maxx)\nprint(maxx)\n", "n = int(input().strip())\nl = list(map(int, input().strip().split(' ')))\nstk = []\nmaxVal = 0\nstk.append(l[0])\nstk.append(l[1])\nmaxVal = stk[-1] ^ stk[-2]\nfor i in l[2:]:\n\twhile len(stk) and stk[-1] < i:\n\t\tstk.pop()\n\tstk.append(i)\n\tif len(stk) >= 2:\n\t\tmaxVal = max(maxVal, stk[-1] ^ stk[-2])\nl = l[::-1]\nstk = []\nstk.append(l[0])\nstk.append(l[1])\nmaxVal = max(maxVal, stk[-1] ^ stk[-2])\nfor i in l[2:]:\n\twhile len(stk) and stk[-1] < i:\n\t\tstk.pop()\n\tstk.append(i)\n\tif len(stk) >= 2:\n\t\tmaxVal = max(maxVal, stk[-1] ^ stk[-2])\nprint(maxVal)\n", "from sys import stdin\nn = int(stdin.readline())\ns = list(map(int, stdin.readline().split()))\nlucky = 0\nstack = []\nfor i in s:\n\twhile stack:\n\t\tlucky = max(lucky, stack[-1] ^ i)\n\t\tif i > stack[-1]:\n\t\t\tstack.pop()\n\t\telse:\n\t\t\tbreak\n\tstack.append(i)\nprint(lucky)\n", "def maxxor(a, b, ans):\n\tt = a ^ b\n\tif t > ans:\n\t\treturn t\n\telse:\n\t\treturn ans\nn = int(input().strip())\narr = list(map(int, input().strip().split()))\ns = list()\ns.append(arr[0])\ns.append(arr[1])\nans = maxxor(arr[0], arr[1], 0)\nindex = 2\nwhile index < n:\n\tif arr[index] > s[-1]:\n\t\twhile arr[index] > s[-1]:\n\t\t\tt = s.pop()\n\t\t\tans = maxxor(arr[index], t, ans)\n\t\t\tif len(s) == 0:\n\t\t\t\tbreak\n\tif len(s) != 0:\n\t\tans = maxxor(arr[index], s[-1], ans)\n\ts.append(arr[index])\n\tindex += 1\nprint(ans)\n", "def solve(array):\n\tst = []\n\tres = array[0] ^ array[1]\n\tfor i in range(n):\n\t\twhile len(st) > 0 and array[i] >= st[-1]:\n\t\t\tst.pop()\n\t\tst.append(array[i])\n\t\tif len(st) >= 2:\n\t\t\tres = max(res, st[-1] ^ st[-2])\n\treturn res\nn = int(input())\narray = list(map(int, input().split()))\nres = solve(array)\nres = max(res, solve(array[::-1]))\nprint(res)\n", "n = int(input())\narr = [int(s) for s in input().split()]\nstck = []\nans = 0\nfor i in arr:\n\tif not stck:\n\t\tstck.append(i)\n\telse:\n\t\twhile stck and i > stck[len(stck) - 1]:\n\t\t\tans = max(ans, i ^ stck[len(stck) - 1])\n\t\t\tstck.pop(len(stck) - 1)\n\t\tif stck:\n\t\t\tans = max(ans, i ^ stck[len(stck) - 1])\n\t\tstck.append(i)\nprint(ans)\n", "def max_ex(nums):\n\tmaximum = float('-inf')\n\tstack = []\n\tfor i in range(len(nums)):\n\t\tif not stack:\n\t\t\tstack.append(nums[i])\n\t\telse:\n\t\t\twhile stack and stack[-1] < nums[i]:\n\t\t\t\tmaximum = max(maximum, stack[-1] ^ nums[i])\n\t\t\t\tstack.pop()\n\t\t\tif stack:\n\t\t\t\tmaximum = max(maximum, stack[-1] ^ nums[i])\n\t\t\tstack.append(nums[i])\n\tif stack:\n\t\ttemp = stack.pop()\n\t\twhile stack:\n\t\t\tmaximum = max(maximum, temp ^ stack[-1])\n\t\t\ttemp = stack.pop()\n\treturn maximum\nn = int(input())\narr = [int(i) for i in input().split()]\nprint(max_ex(arr))\n", "import sys\nn = int(input())\na = [int(x) for x in input().strip().split(' ')]\nst = [a[0]]\nmax1 = -sys.maxsize\nfor i in range(1, n):\n\twhile len(st) > 0:\n\t\tif a[i] < st[len(st) - 1]:\n\t\t\tmax1 = max(max1, a[i] ^ st[len(st) - 1])\n\t\t\tbreak\n\t\telse:\n\t\t\tmax1 = max(max1, a[i] ^ st[len(st) - 1])\n\t\t\tst.pop()\n\tst.append(a[i])\nprint(max1)\n"]

question:
Bike loves looking for the second maximum element in the sequence. The second maximum element in the sequence of distinct numbers x_{1}, x_{2}, ..., x_{k} (k > 1) is such maximum element x_{j}, that the following inequality holds: ![image](1.png).
The lucky number of the sequence of distinct positive integers x_{1}, x_{2}, ..., x_{k} (k > 1) is the number that is equal to the bitwise excluding OR of the maximum element of the sequence and the second maximum element of the sequence.
You've got a sequence of distinct positive integers s_{1}, s_{2}, ..., s_{n} (n > 1). Let's denote sequence s_{l}, s_{l + 1}, ..., s_{r} as s[l..r] (1 ≤ l < r ≤ n). Your task is to find the maximum number among all lucky numbers of sequences s[l..r].
Note that as all numbers in sequence s are distinct, all the given definitions make sence.

Input
The first line contains integer n (1 < n ≤ 10^{5}). The second line contains n distinct integers s_{1}, s_{2}, ..., s_{n} (1 ≤ s_{i} ≤ 10^{9}).

Output
Print a single integer — the maximum lucky number among all lucky numbers of sequences s[l..r].

Examples
Input
5
5 2 1 4 3

Output
7

Input
5
9 8 3 5 7

Output
15

Note
For the first sample you can choose s[4..5] = {4, 3} and its lucky number is (4 xor 3) = 7. You can also choose s[1..2].
For the second sample you must choose s[2..5] = {8, 3, 5, 7}.

source: codeforces

raw_problem:
B. Maximum Xor Secondary

time limit per test
1 second

memory limit per test
256 megabytes

input
standard input

output
standard output

Bike loves looking for the second maximum element in the sequence. The second maximum element in the sequence of distinct numbers x1, x2, ..., xk (k > 1) is such maximum element xj, that the following inequality holds: .

The lucky number of the sequence of distinct positive integers x1, x2, ..., xk (k > 1) is the number that is equal to the bitwise excluding OR of the maximum element of the sequence and the second maximum element of the sequence.

You've got a sequence of distinct positive integers s1, s2, ..., sn (n > 1). Let's denote sequence sl, sl + 1, ..., sr as s[l..r] (1 ≤ l < r ≤ n). Your task is to find the maximum number among all lucky numbers of sequences s[l..r].

Note that as all numbers in sequence s are distinct, all the given definitions make sence.

Input

The first line contains integer n (1 < n ≤ 105). The second line contains n distinct integers s1, s2, ..., sn (1 ≤ si ≤ 109).

Output

Print a single integer — the maximum lucky number among all lucky numbers of sequences s[l..r].

Examples

Input

5
5 2 1 4 3

Output

7

Input

5
9 8 3 5 7

Output

15

Note

For the first sample you can choose s[4..5] = {4, 3} and its lucky number is (4 xor 3) = 7. You can also choose s[1..2].

For the second sample you must choose s[2..5] = {8, 3, 5, 7}.

tags: ['Amortized analysis', 'Data structures', 'Implementation']

skill_types: ['Data structures', 'Amortized analysis']

raw_tags: ['two pointers', 'data structures', 'implementation']

data_split: test


D. Rap God

problem_index: D

time_limit: 7 seconds

memory_limit: 256 megabytes

note:
Here's the tree of first sample testcase:
![image](images/cf_786_D/2.png)
Here's the tree of second sample testcase:
![image](images/cf_786_D/3.png)
In this test:
str(8, 1) = poo  str(8, 2) = poe  str(8, 3) = po  str(8, 4) = pop  str(8, 5) = popd  str(8, 6) = popp  str(8, 7) = p
So, for the first query, ![image](images/cf_786_D/4.png) and for the third query ![image](images/cf_786_D/5.png) is the answer.

source: codeforces

raw_problem:
D. Rap God

time limit per test
7 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Rick is in love with Unity. But Mr. Meeseeks also love Unity, so Rick and Mr. Meeseeks are "love rivals".

Unity loves rap, so it decided that they have to compete in a rap game (battle) in order to choose the best. Rick is too nerds, so instead he's gonna make his verse with running his original algorithm on lyrics "Rap God" song.

His algorithm is a little bit complicated. He's made a tree with n vertices numbered from 1 to n and there's a lowercase english letter written on each edge. He denotes str(a, b) to be the string made by writing characters on edges on the shortest path from a to b one by one (a string of length equal to distance of a to b). Note that str(a, b) is reverse of str(b, a) and str(a, a) is empty.

 In order to make the best verse he can, he needs to answer some queries, but he's not a computer scientist and is not able to answer those queries, so he asked you to help him. Each query is characterized by two vertices x and y (x ≠ y). Answer to this query is the number of vertices like z such that z ≠ x, z ≠ y and str(x, y) is lexicographically larger than str(x, z).

String x  =  x1x2...x|x| is lexicographically larger than string y  =  y1y2...y|y|, if either |x|  >  |y| and x1  =  y1,  x2  =  y2,  ...,  x|y|  =  y|y|, or exists such number r (r  <  |x|,  r  <  |y|), that x1  =  y1,  x2  =  y2,  ...,  xr  =  yr and xr  +  1  >  yr  +  1. Characters are compared like their ASCII codes (or alphabetic order).

Help Rick get the girl (or whatever gender Unity has).

Input

The first line of input contain two integers n and q (2 ≤ n ≤ 20000, 1 ≤ q ≤ 20000) — number of vertices in tree and number of queries respectively.

The next n - 1 lines contain the edges. Each line contains two integers v and u (endpoints of the edge) followed by an English lowercase letter c (1 ≤ v, u ≤ n, v ≠ u).

The next q line contain the queries. Each line contains two integers x and y (1 ≤ x, y ≤ n, x ≠ y).

Output

Print the answer for each query in one line.

Examples

Input

4 3
4 1 t
3 2 p
1 2 s
3 2
1 3
2 1

Output

0
1
1

Input

8 4
4 6 p
3 7 o
7 8 p
4 5 d
1 3 o
4 3 p
3 2 e
8 6
3 7
8 1
4 3

Output

6
1
3
1

Note

Here's the tree of first sample testcase:

Here's the tree of second sample testcase:

In this test:

 str(8, 1) = poo

 str(8, 2) = poe

 str(8, 3) = po

 str(8, 4) = pop

 str(8, 5) = popd

 str(8, 6) = popp

 str(8, 7) = p

So, for the first query,  and for the third query  is the answer.

question:
Rick is in love with Unity. But Mr. Meeseeks also love Unity, so Rick and Mr. Meeseeks are "love rivals".
Unity loves rap, so it decided that they have to compete in a rap game (battle) in order to choose the best. Rick is too nerds, so instead he's gonna make his verse with running his original algorithm on lyrics "Rap God" song.
 His algorithm is a little bit complicated. He's made a tree with n vertices numbered from 1 to n and there's a lowercase english letter written on each edge. He denotes str(a, b) to be the string made by writing characters on edges on the shortest path from a to b one by one (a string of length equal to distance of a to b). Note that str(a, b) is reverse of str(b, a) and str(a, a) is empty.
 In order to make the best verse he can, he needs to answer some queries, but he's not a computer scientist and is not able to answer those queries, so he asked you to help him. Each query is characterized by two vertices x and y (x ≠ y). Answer to this query is the number of vertices like z such that z ≠ x, z ≠ y and str(x, y) is lexicographically larger than str(x, z).
String x  =  x_{1}x_{2}...x_{|x|} is lexicographically larger than string y  =  y_{1}y_{2}...y_{|y|}, if either |x|  >  |y| and x_{1}  =  y_{1},  x_{2}  =  y_{2},  ...,  x_{|y|}  =  y_{|y|}, or exists such number r (r  <  |x|,  r  <  |y|), that x_{1}  =  y_{1},  x_{2}  =  y_{2},  ...,  x_{r}  =  y_{r} and x_{r  +  1}  >  y_{r  +  1}. Characters are compared like their ASCII codes (or alphabetic order).
Help Rick get the girl (or whatever gender Unity has).

Input
The first line of input contain two integers n and q (2 ≤ n ≤ 20000, 1 ≤ q ≤ 20000) — number of vertices in tree and number of queries respectively.
The next n - 1 lines contain the edges. Each line contains two integers v and u (endpoints of the edge) followed by an English lowercase letter c (1 ≤ v, u ≤ n, v ≠ u).
The next q line contain the queries. Each line contains two integers x and y (1 ≤ x, y ≤ n, x ≠ y).

Output
Print the answer for each query in one line.

Examples
Input
4 3
4 1 t
3 2 p
1 2 s
3 2
1 3
2 1

Output
0
1
1

Input
8 4
4 6 p
3 7 o
7 8 p
4 5 d
1 3 o
4 3 p
3 2 e
8 6
3 7
8 1
4 3

Output
6
1
3
1

Note
Here's the tree of first sample testcase:
 ![image](2.png) Here's the tree of second sample testcase:
 ![image](3.png) In this test:
 -  str(8, 1) = poo -  str(8, 2) = poe -  str(8, 3) = po -  str(8, 4) = pop -  str(8, 5) = popd -  str(8, 6) = popp -  str(8, 7) = p So, for the first query, ![image](4.png) and for the third query ![image](5.png) is the answer.

tags: ['Tree algorithms', 'Data structures', 'Graph traversal', 'String algorithms']

skill_types: ['Data structures']

raw_tags: ['data structures', 'dfs and similar', 'strings', 'hashing', 'trees']

image_tags: Graph Graph Math Others

data_split: test


solutions: ["for t in range(int(input())):\n\t(N, M) = map(int, input().split())\n\tif M < N:\n\t\t(N, M) = (M, N)\n\tif N == 1:\n\t\tprint(M)\n\telse:\n\t\tres = M // 6 * 4\n\t\tif M % 6 > 0:\n\t\t\tif M % 6 == 1:\n\t\t\t\tres += 2\n\t\t\telif N == 3 and M > 12 and (M % 6 == 2):\n\t\t\t\tres += 3\n\t\t\telse:\n\t\t\t\tres += 4\n\t\tprint(res)\n", "def knights(n, m):\n\tif n == 1:\n\t\treturn m\n\telif n == 2:\n\t\tif m == 1:\n\t\t\treturn 2\n\t\telse:\n\t\t\ttable = [0, 2, 4, 4, 4, 4, 4]\n\t\t\tif m <= 6:\n\t\t\t\treturn table[m]\n\t\t\telse:\n\t\t\t\tk = 0\n\t\t\t\twhile m > 6:\n\t\t\t\t\tm -= 6\n\t\t\t\t\tk += 4\n\t\t\t\treturn k + table[m]\n\telse:\n\t\ttable = [0, 3, 4, 4, 4, 4, 4, 6, 8, 8, 8, 8, 8, 10, 11, 12, 12, 12, 12]\n\t\tif m <= 18:\n\t\t\treturn table[m]\n\t\telse:\n\t\t\tk = 0\n\t\t\twhile m > 18:\n\t\t\t\tk += 4\n\t\t\t\tm -= 6\n\t\t\treturn k + table[m]\nt = int(input())\nwhile t > 0:\n\t(n, m) = map(int, input().split())\n\tprint(knights(n, m))\n\tt -= 1\n"]

raw_tags: ['Mathematics', 'Special', 'Advanced DP', 'Advanced Algorithms', 'Chess', 'Case work', 'DP Bitmask', 'Bit Manipulation']

source: codechef

tags: ['Dynamic programming', 'Bit manipulation', 'Mathematics', 'Ad-hoc']

skill_types: ['Dynamic programming', 'Bit manipulation']

time_limit: 1 seconds

memory_limit: 50000 bytes

raw_problem:
Read problems statements in mandarin chinese, russian and vietnamese as well.

Given a board of N rows and M columns, place the minimum number of knights such that every cell either contains a knight or is attacked by at least one knight.

Like in standard chess, a knight attacks every cell that is two squares away horizontally and one square vertically, or two squares vertically and one square horizontally.

Input

The first line of input contains one number T, the number of test cases.
Each test case contains two integers N and M, the dimensions of the board.

Output

For each test case print the minimum number of knights required to cover every cell of the board.

Constraints

1 ≤ T ≤ 150

1 ≤ N ≤ 3

1 ≤ M ≤ 50

Example

Input:
1
2 4

Output:
4

Explanation

One optimal configuration is:

Cells (1, 1), (1, 2), (4, 1) and (4, 2) contain knights. Cell (2, 1) is attacked by the knight in cell (4, 2). Cell (2, 2) is attacked by the knight in cell (4, 1). Cell (3, 1) is attacked by the knight in cell (1, 2). And cell (3, 2) is attacked by the knight in cell (1, 1).

So every cell either contains a knight or is attacked by at least one knight, hence this is a valid configuration. There is no valid configuration with fewer knights, and so the answer is 4.

All submissions for this problem are available.

question:
Read problems statements in mandarin chinese, russian and vietnamese as well.

Given a board of N rows and M columns, place the minimum number of knights such that every cell either contains a knight or is attacked by at least one knight.

Like in standard chess, a knight attacks every cell that is two squares away horizontally and one square vertically, or two squares vertically and one square horizontally.

Input

The first line of input contains one number T, the number of test cases.
Each test case contains two integers N and M, the dimensions of the board.

Output

For each test case print the minimum number of knights required to cover every cell of the board.

Constraints
- 1 ≤ T ≤ 150
- 1 ≤ N ≤ 3
- 1 ≤ M ≤ 50
Example

Input:
1
2 4

Output:
4

Explanation
One optimal configuration is:

![image](1.png)

Cells (1, 1), (1, 2), (4, 1) and (4, 2) contain knights. Cell (2, 1) is attacked by the knight in cell (4, 2). Cell (2, 2) is attacked by the knight in cell (4, 1). Cell (3, 1) is attacked by the knight in cell (1, 2). And cell (3, 2) is attacked by the knight in cell (1, 1).
So every cell either contains a knight or is attacked by at least one knight, hence this is a valid configuration. There is no valid configuration with fewer knights, and so the answer is 4.
All submissions for this problem are available.

data_split: test


C. Andryusha and Colored Balloons

problem_index: C

time_limit: 2 seconds

memory_limit: 256 megabytes

note:
In the first sample the park consists of three squares: 1 → 3 → 2. Thus, the balloon colors have to be distinct.
![image](images/cf_780_C/1.png) Illustration for the first sample.
In the second example there are following triples of consequently connected squares:
1 → 3 → 2  1 → 3 → 4  1 → 3 → 5  2 → 3 → 4  2 → 3 → 5  4 → 3 → 5
![image](images/cf_780_C/2.png) Illustration for the second sample.
In the third example there are following triples:
1 → 2 → 3  2 → 3 → 4  3 → 4 → 5
![image](images/cf_780_C/3.png) Illustration for the third sample.

solutions: ["import os\nimport sys\nfrom io import BytesIO, IOBase\nfrom math import log2, ceil, sqrt, gcd, log\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\ng = lambda : input().strip()\ngl = lambda : g().split()\ngil = lambda : [int(var) for var in gl()]\ngfl = lambda : [float(var) for var in gl()]\ngcl = lambda : list(g())\ngbs = lambda : [int(var) for var in g()]\nrr = lambda x: reversed(range(x))\nmod = int(1000000000.0) + 7\ninf = float('inf')\n(n,) = gil()\nadj = [[] for _ in range(n + 1)]\nfor _ in range(n - 1):\n\t(x, y) = gil()\n\tadj[x].append(y)\n\tadj[y].append(x)\nused = set()\nclr = [0] * (n + 1)\nmaxVal = 1\ntoClr = []\nst = [1]\nvis = [0] * (n + 1)\nwhile st:\n\ti = st.pop()\n\tif vis[i]:\n\t\tcontinue\n\tvis[i] = 1\n\tptr = 1\n\tused.add(clr[i])\n\tif clr[i] == 0:\n\t\ttoClr.append(i)\n\tfor y in adj[i]:\n\t\tif clr[y]:\n\t\t\tused.add(clr[y])\n\t\telse:\n\t\t\tst.append(y)\n\t\t\ttoClr.append(y)\n\twhile toClr:\n\t\twhile ptr in used:\n\t\t\tptr += 1\n\t\tused.add(ptr)\n\t\tclr[toClr.pop()] = ptr\n\t\tmaxVal = max(maxVal, ptr)\n\t\tptr += 1\n\tused.clear()\nprint(maxVal)\nprint(*clr[1:])\n", "import sys, os, io\n\ndef rs():\n\treturn sys.stdin.readline().rstrip()\n\ndef ri():\n\treturn int(sys.stdin.readline())\n\ndef ria():\n\treturn list(map(int, sys.stdin.readline().split()))\n\ndef ws(s):\n\tsys.stdout.write(s + '\\n')\n\ndef wi(n):\n\tsys.stdout.write(str(n) + '\\n')\n\ndef wia(a):\n\tsys.stdout.write(' '.join([str(x) for x in a]) + '\\n')\nimport math, datetime, functools, itertools, operator, bisect, fractions, statistics\nfrom collections import deque, defaultdict, OrderedDict, Counter\nfrom fractions import Fraction\nfrom decimal import Decimal\nfrom sys import stdout\nfrom heapq import heappush, heappop, heapify, _heapify_max, _heappop_max, nsmallest, nlargest\nINF = 999999999999999999999999\nalphabets = 'abcdefghijklmnopqrstuvwxyz'\n\nclass SortedList:\n\n\tdef __init__(self, iterable=[], _load=200):\n\t\tvalues = sorted(iterable)\n\t\tself._len = _len = len(values)\n\t\tself._load = _load\n\t\tself._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]\n\t\tself._list_lens = [len(_list) for _list in _lists]\n\t\tself._mins = [_list[0] for _list in _lists]\n\t\tself._fen_tree = []\n\t\tself._rebuild = True\n\n\tdef _fen_build(self):\n\t\tself._fen_tree[:] = self._list_lens\n\t\t_fen_tree = self._fen_tree\n\t\tfor i in range(len(_fen_tree)):\n\t\t\tif i | i + 1 < len(_fen_tree):\n\t\t\t\t_fen_tree[i | i + 1] += _fen_tree[i]\n\t\tself._rebuild = False\n\n\tdef _fen_update(self, index, value):\n\t\tif not self._rebuild:\n\t\t\t_fen_tree = self._fen_tree\n\t\t\twhile index < len(_fen_tree):\n\t\t\t\t_fen_tree[index] += value\n\t\t\t\tindex |= index + 1\n\n\tdef _fen_query(self, end):\n\t\tif self._rebuild:\n\t\t\tself._fen_build()\n\t\t_fen_tree = self._fen_tree\n\t\tx = 0\n\t\twhile end:\n\t\t\tx += _fen_tree[end - 1]\n\t\t\tend &= end - 1\n\t\treturn x\n\n\tdef _fen_findkth(self, k):\n\t\t_list_lens = self._list_lens\n\t\tif k < _list_lens[0]:\n\t\t\treturn (0, k)\n\t\tif k >= self._len - _list_lens[-1]:\n\t\t\treturn (len(_list_lens) - 1, k + _list_lens[-1] - self._len)\n\t\tif self._rebuild:\n\t\t\tself._fen_build()\n\t\t_fen_tree = self._fen_tree\n\t\tidx = -1\n\t\tfor d in reversed(range(len(_fen_tree).bit_length())):\n\t\t\tright_idx = idx + (1 << d)\n\t\t\tif right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:\n\t\t\t\tidx = right_idx\n\t\t\t\tk -= _fen_tree[idx]\n\t\treturn (idx + 1, k)\n\n\tdef _delete(self, pos, idx):\n\t\t_lists = self._lists\n\t\t_mins = self._mins\n\t\t_list_lens = self._list_lens\n\t\tself._len -= 1\n\t\tself._fen_update(pos, -1)\n\t\tdel _lists[pos][idx]\n\t\t_list_lens[pos] -= 1\n\t\tif _list_lens[pos]:\n\t\t\t_mins[pos] = _lists[pos][0]\n\t\telse:\n\t\t\tdel _lists[pos]\n\t\t\tdel _list_lens[pos]\n\t\t\tdel _mins[pos]\n\t\t\tself._rebuild = True\n\n\tdef _loc_left(self, value):\n\t\tif not self._len:\n\t\t\treturn (0, 0)\n\t\t_lists = self._lists\n\t\t_mins = self._mins\n\t\t(lo, pos) = (-1, len(_lists) - 1)\n\t\twhile lo + 1 < pos:\n\t\t\tmi = lo + pos >> 1\n\t\t\tif value <= _mins[mi]:\n\t\t\t\tpos = mi\n\t\t\telse:\n\t\t\t\tlo = mi\n\t\tif pos and value <= _lists[pos - 1][-1]:\n\t\t\tpos -= 1\n\t\t_list = _lists[pos]\n\t\t(lo, idx) = (-1, len(_list))\n\t\twhile lo + 1 < idx:\n\t\t\tmi = lo + idx >> 1\n\t\t\tif value <= _list[mi]:\n\t\t\t\tidx = mi\n\t\t\telse:\n\t\t\t\tlo = mi\n\t\treturn (pos, idx)\n\n\tdef _loc_right(self, value):\n\t\tif not self._len:\n\t\t\treturn (0, 0)\n\t\t_lists = self._lists\n\t\t_mins = self._mins\n\t\t(pos, hi) = (0, len(_lists))\n\t\twhile pos + 1 < hi:\n\t\t\tmi = pos + hi >> 1\n\t\t\tif value < _mins[mi]:\n\t\t\t\thi = mi\n\t\t\telse:\n\t\t\t\tpos = mi\n\t\t_list = _lists[pos]\n\t\t(lo, idx) = (-1, len(_list))\n\t\twhile lo + 1 < idx:\n\t\t\tmi = lo + idx >> 1\n\t\t\tif value < _list[mi]:\n\t\t\t\tidx = mi\n\t\t\telse:\n\t\t\t\tlo = mi\n\t\treturn (pos, idx)\n\n\tdef add(self, value):\n\t\t_load = self._load\n\t\t_lists = self._lists\n\t\t_mins = self._mins\n\t\t_list_lens = self._list_lens\n\t\tself._len += 1\n\t\tif _lists:\n\t\t\t(pos, idx) = self._loc_right(value)\n\t\t\tself._fen_update(pos, 1)\n\t\t\t_list = _lists[pos]\n\t\t\t_list.insert(idx, value)\n\t\t\t_list_lens[pos] += 1\n\t\t\t_mins[pos] = _list[0]\n\t\t\tif _load + _load < len(_list):\n\t\t\t\t_lists.insert(pos + 1, _list[_load:])\n\t\t\t\t_list_lens.insert(pos + 1, len(_list) - _load)\n\t\t\t\t_mins.insert(pos + 1, _list[_load])\n\t\t\t\t_list_lens[pos] = _load\n\t\t\t\tdel _list[_load:]\n\t\t\t\tself._rebuild = True\n\t\telse:\n\t\t\t_lists.append([value])\n\t\t\t_mins.append(value)\n\t\t\t_list_lens.append(1)\n\t\t\tself._rebuild = True\n\n\tdef discard(self, value):\n\t\t_lists = self._lists\n\t\tif _lists:\n\t\t\t(pos, idx) = self._loc_right(value)\n\t\t\tif idx and _lists[pos][idx - 1] == value:\n\t\t\t\tself._delete(pos, idx - 1)\n\n\tdef remove(self, value):\n\t\t_len = self._len\n\t\tself.discard(value)\n\t\tif _len == self._len:\n\t\t\traise ValueError('{0!r} not in list'.format(value))\n\n\tdef pop(self, index=-1):\n\t\t(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)\n\t\tvalue = self._lists[pos][idx]\n\t\tself._delete(pos, idx)\n\t\treturn value\n\n\tdef bisect_left(self, value):\n\t\t(pos, idx) = self._loc_left(value)\n\t\treturn self._fen_query(pos) + idx\n\n\tdef bisect_right(self, value):\n\t\t(pos, idx) = self._loc_right(value)\n\t\treturn self._fen_query(pos) + idx\n\n\tdef count(self, value):\n\t\treturn self.bisect_right(value) - self.bisect_left(value)\n\n\tdef __len__(self):\n\t\treturn self._len\n\n\tdef __getitem__(self, index):\n\t\t(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)\n\t\treturn self._lists[pos][idx]\n\n\tdef __delitem__(self, index):\n\t\t(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)\n\t\tself._delete(pos, idx)\n\n\tdef __contains__(self, value):\n\t\t_lists = self._lists\n\t\tif _lists:\n\t\t\t(pos, idx) = self._loc_left(value)\n\t\t\treturn idx < len(_lists[pos]) and _lists[pos][idx] == value\n\t\treturn False\n\n\tdef __iter__(self):\n\t\treturn (value for _list in self._lists for value in _list)\n\n\tdef __reversed__(self):\n\t\treturn (value for _list in reversed(self._lists) for value in reversed(_list))\n\n\tdef __repr__(self):\n\t\treturn 'SortedList({0})'.format(list(self))\n\nclass SegTree:\n\n\tdef __init__(self, n):\n\t\tself.N = 1 << n.bit_length()\n\t\tself.tree = [0] * (self.N << 1)\n\n\tdef update(self, i, j, v):\n\t\ti += self.N\n\t\tj += self.N\n\t\twhile i <= j:\n\t\t\tif i % 2 == 1:\n\t\t\t\tself.tree[i] += v\n\t\t\tif j % 2 == 0:\n\t\t\t\tself.tree[j] += v\n\t\t\t(i, j) = (i + 1 >> 1, j - 1 >> 1)\n\n\tdef query(self, i):\n\t\tv = 0\n\t\ti += self.N\n\t\twhile i > 0:\n\t\t\tv += self.tree[i]\n\t\t\ti >>= 1\n\t\treturn v\n\ndef SieveOfEratosthenes(limit):\n\tisPrime = [True] * (limit + 1)\n\tisPrime[0] = isPrime[1] = False\n\tprimes = []\n\tfor i in range(2, limit + 1):\n\t\tif not isPrime[i]:\n\t\t\tcontinue\n\t\tprimes += [i]\n\t\tfor j in range(i * i, limit + 1, i):\n\t\t\tisPrime[j] = False\n\treturn primes\n\ndef main():\n\tmod = 1000000007\n\tstarttime = datetime.datetime.now()\n\tif os.path.exists('input.txt'):\n\t\tsys.stdin = open('input.txt', 'r')\n\t\tsys.stdout = open('output.txt', 'w')\n\ttc = 1\n\tfor _ in range(tc):\n\t\tn = ri()\n\t\tcol = [0] * (n + 1)\n\t\tcol[0] = INF\n\t\tcol[1] = 1\n\t\tpar = [0] * (n + 1)\n\t\tgraph = [[] for i in range(n + 1)]\n\t\tfor i in range(n - 1):\n\t\t\t(x, y) = ria()\n\t\t\tgraph[x].append(y)\n\t\t\tgraph[y].append(x)\n\n\t\tdef dfs():\n\t\t\tmxc = 1\n\t\t\tvisited = [False] * (n + 1)\n\t\t\tstart = 1\n\t\t\tstack = [start]\n\t\t\twhile stack:\n\t\t\t\tstart = stack[-1]\n\t\t\t\tif not visited[start]:\n\t\t\t\t\tvisited[start] = True\n\t\t\t\t\t(a, b) = (col[par[start]], col[start])\n\t\t\t\t\tind = 1\n\t\t\t\t\tfor child in graph[start]:\n\t\t\t\t\t\tif not visited[child]:\n\t\t\t\t\t\t\tpar[child] = start\n\t\t\t\t\t\t\twhile ind != len(graph[start]) + 2:\n\t\t\t\t\t\t\t\tif ind != a and ind != b:\n\t\t\t\t\t\t\t\t\tcol[child] = ind\n\t\t\t\t\t\t\t\t\tmxc = max(mxc, ind)\n\t\t\t\t\t\t\t\t\tind += 1\n\t\t\t\t\t\t\t\t\tbreak\n\t\t\t\t\t\t\t\tind += 1\n\t\t\t\t\t\t\tstack.append(child)\n\t\t\t\telse:\n\t\t\t\t\tstack.pop()\n\t\t\treturn mxc\n\t\twi(dfs())\n\t\twia(col[1:])\n\tendtime = datetime.datetime.now()\n\ttime = (endtime - starttime).total_seconds() * 1000\n\tif os.path.exists('input.txt'):\n\t\tprint('Time:', time, 'ms')\n\nclass FastReader(io.IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, fd, chunk_size=1024 * 8):\n\t\tself._fd = fd\n\t\tself._chunk_size = chunk_size\n\t\tself.buffer = io.BytesIO()\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self, size=-1):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\nclass FastWriter(io.IOBase):\n\n\tdef __init__(self, fd):\n\t\tself._fd = fd\n\t\tself.buffer = io.BytesIO()\n\t\tself.write = self.buffer.write\n\n\tdef flush(self):\n\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass FastStdin(io.IOBase):\n\n\tdef __init__(self, fd=0):\n\t\tself.buffer = FastReader(fd)\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n\nclass FastStdout(io.IOBase):\n\n\tdef __init__(self, fd=1):\n\t\tself.buffer = FastWriter(fd)\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.flush = self.buffer.flush\nsys.stdin = FastStdin()\nsys.stdout = FastStdout()\nmain()\n", "import collections\n\ndef doit():\n\tN = int(input())\n\tgraph = dict()\n\tfor n in range(N):\n\t\tgraph[n] = list()\n\tfor n in range(N - 1):\n\t\t(a, b) = map(int, input().split())\n\t\tgraph[a - 1].append(b - 1)\n\t\tgraph[b - 1].append(a - 1)\n\tmsize = 0\n\tfor k in graph:\n\t\tmsize = max(msize, len(graph[k]))\n\tprint(msize + 1)\n\troot = 0\n\tcolors = [0 for x in range(N)]\n\tcolors[root] = 1\n\tparents = [0 for x in range(N)]\n\tparents[root] = root\n\n\tdef colorgenerator(c1, c2):\n\t\tcolorindex = 0\n\t\twhile colorindex < msize + 1:\n\t\t\tcolorindex += 1\n\t\t\tif colorindex == c1 or colorindex == c2:\n\t\t\t\tcontinue\n\t\t\tyield colorindex\n\tqueue = collections.deque([root])\n\twhile queue:\n\t\tvertex = queue.popleft()\n\t\tcolor = colorgenerator(colors[vertex], colors[parents[vertex]])\n\t\tfor neighbour in graph[vertex]:\n\t\t\tif neighbour == parents[vertex]:\n\t\t\t\tcontinue\n\t\t\tparents[neighbour] = vertex\n\t\t\tcolors[neighbour] = next(color)\n\t\t\tqueue.append(neighbour)\n\tprint(' '.join(map(str, colors)))\ndoit()\n", "import bisect\nimport collections\nimport copy\nimport functools\nimport heapq\nimport itertools\nimport math\nimport random\nimport re\nimport sys\nimport time\nimport string\nfrom typing import List, Mapping\nsys.setrecursionlimit(999999)\ncs = [0, 1] + [0] * 10 ** 6\nn = int(input())\ng = collections.defaultdict(list)\nfor _ in range(n - 1):\n\t(u, v) = map(int, input().split())\n\tg[u].append(v)\n\tg[v].append(u)\nq = collections.deque([[1, 0]])\nwhile q:\n\t(cur, fa) = q.popleft()\n\ts = set()\n\ts.add(cs[cur])\n\tif fa:\n\t\ts.add(cs[fa])\n\tk = 1\n\tfor nc in g[cur]:\n\t\tif nc == fa:\n\t\t\tcontinue\n\t\twhile k in s:\n\t\t\tk += 1\n\t\tcs[nc] = k\n\t\ts.add(k)\n\t\tq.append([nc, cur])\nprint(max(cs[1:n + 1]))\nprint(*cs[1:n + 1])\n", "import os\nimport sys\nfrom io import BytesIO, IOBase\nimport heapq as h\nfrom bisect import bisect_left, bisect_right\nfrom types import GeneratorType\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\timport os\n\t\tself.os = os\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tself.os.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\nimport collections as col\nimport math, string\n\ndef getInts():\n\treturn [int(s) for s in input().split()]\n\ndef getInt():\n\treturn int(input())\n\ndef getStrs():\n\treturn [s for s in input().split()]\n\ndef getStr():\n\treturn input()\n\ndef listStr():\n\treturn list(input())\nMOD = 10 ** 9 + 7\n\ndef solve():\n\tN = getInt()\n\tgraph = col.defaultdict(set)\n\tfor n in range(N - 1):\n\t\t(U, V) = getInts()\n\t\tU -= 1\n\t\tV -= 1\n\t\tgraph[U].add(V)\n\t\tgraph[V].add(U)\n\n\tdef bfs(node):\n\t\timport collections as col\n\t\tnodes.remove(node)\n\t\tcols[node] = 1\n\t\tqueue = col.deque([])\n\t\tqueue.append((node, 1, -1, -1))\n\t\twhile queue:\n\t\t\t(node, colour, parent, parent_col) = queue.popleft()\n\t\t\ty = set([j + 1 for j in range(len(graph[node]) + 1)])\n\t\t\tif colour in y:\n\t\t\t\ty.remove(colour)\n\t\t\tif parent_col in y:\n\t\t\t\ty.remove(parent_col)\n\t\t\tfor neighbour in graph[node]:\n\t\t\t\tif neighbour in nodes:\n\t\t\t\t\tnodes.remove(neighbour)\n\t\t\t\t\tnew_col = next(iter(y))\n\t\t\t\t\ty.remove(new_col)\n\t\t\t\t\tcols[neighbour] = new_col\n\t\t\t\t\tqueue.append((neighbour, new_col, node, colour))\n\t\treturn\n\tnodes = set([j for j in range(N)])\n\tcols = [-1] * N\n\tbfs(0)\n\tprint(max(cols))\n\tprint(*cols)\n\treturn\nsolve()\n", "from collections import deque\nn = int(input())\ng = []\nvisited = []\ncolor = []\nmax_child_color = []\nparent = []\n\ndef initialize():\n\tfor i in range(n + 10):\n\t\tg.append([])\n\t\tvisited.append(False)\n\t\tcolor.append(0)\n\t\tmax_child_color.append(0)\n\t\tparent.append(0)\n\tfor i in range(n - 1):\n\t\t(u, v) = map(int, input().split())\n\t\tg[u] += [v]\n\t\tg[v] += [u]\n\ndef get_color(u):\n\tfor i in range(max_child_color[u] + 1, n + 1):\n\t\tif i != color[parent[u]] and i != color[u]:\n\t\t\tmax_child_color[u] = i\n\t\t\treturn i\n\ndef bfs(start):\n\tvisited[start] = True\n\tcolor[start] = 1\n\tq = deque()\n\tq.append(start)\n\twhile q:\n\t\tu = q.popleft()\n\t\tfor v in g[u]:\n\t\t\tparent[v] = u\n\t\t\tif not visited[v]:\n\t\t\t\tvisited[v] = True\n\t\t\t\tcolor[v] = get_color(u)\n\t\t\t\tq.append(v)\ninitialize()\nbfs(1)\nprint(max(color))\nc_string = ''\nfor i in range(1, n + 1):\n\tc_string += str(color[i]) + ' '\nprint(c_string)\n", "n = int(input())\nfrom collections import defaultdict, deque\ng = defaultdict(list)\nfrom sys import stdin\nfor i in range(n - 1):\n\t(h, m) = map(int, stdin.readline().split())\n\tg[h - 1].append(m - 1)\n\tg[m - 1].append(h - 1)\nvis = [0] * n\nc = [0] * n\nc[0] = 1\nq = deque()\nq.append(0)\nwhile q:\n\tnode = q.popleft()\n\tvis[node] = 1\n\ts = set()\n\tfor i in g[node]:\n\t\tif vis[i] == 1:\n\t\t\ts.add(c[i])\n\tp = []\n\ts.add(c[node])\n\tl = len(s)\n\tj = 0\n\tk = 1\n\twhile l + j <= len(g[node]) + 2:\n\t\tr = 0\n\t\twhile r == 0:\n\t\t\tif k not in s:\n\t\t\t\tp.append(k)\n\t\t\t\tr = 1\n\t\t\tk += 1\n\t\tj += 1\n\tj = 0\n\tfor i in g[node]:\n\t\tif vis[i] == 0:\n\t\t\tc[i] = p[j]\n\t\t\tj += 1\n\t\t\tq.append(i)\nprint(max(c))\nprint(*c)\n", "import sys\nn = int(sys.stdin.readline())\ne = dict()\nw = dict()\nfor i in range(1, n + 1):\n\tw[i] = -1\n\te[i] = set()\nfor i in range(n - 1):\n\t(a, b) = map(int, sys.stdin.readline().split())\n\te[a].add(b)\n\te[b].add(a)\nfirst = 0\nfor i in e:\n\tif len(e[i]) == 1:\n\t\tfirst = i\n\t\tbreak\nsosed = set()\nposetil = set()\nsosed.add(first)\nposetil.add(first)\nw[first] = 1\nwhile len(sosed) > 0:\n\tsosed2 = set()\n\tfor i in sosed:\n\t\tNO = set()\n\t\tNO.add(w[i])\n\t\tbad = set()\n\t\tfor j in e[i]:\n\t\t\tif len(e[j]) > 1:\n\t\t\t\tsosed2.add(j)\n\t\t\tif w[j] != -1:\n\t\t\t\tNO.add(w[j])\n\t\t\telse:\n\t\t\t\tbad.add(j)\n\t\tx = 1\n\t\tfor j in bad:\n\t\t\tif w[j] == -1:\n\t\t\t\twhile x in NO:\n\t\t\t\t\tx += 1\n\t\t\t\tw[j] = x\n\t\t\t\tNO.add(x)\n\t\tposetil.add(i)\n\tsosed2 -= posetil\n\tsosed = sosed2.copy()\nans = []\nlol = set()\nfor i in range(1, n + 1):\n\tans.append(w[i])\n\tlol.add(w[i])\nprint(len(lol))\nprint(*ans)\n", "n = int(input())\ng = [[] for i in range(n)]\nfor _ in range(n - 1):\n\t(x, y) = map(int, input().split())\n\tg[x - 1].append(y - 1)\n\tg[y - 1].append(x - 1)\nl = 0\nfor i in range(n):\n\tl = max(l, len(g[i]) + 1)\nq = [0]\npaint = [-1] * n\npaint[0] = 1\nwhile q:\n\tver = q.pop()\n\tuse = set()\n\tuse.add(paint[ver])\n\tfor to in g[ver]:\n\t\tuse.add(paint[to])\n\tarr = []\n\tfor i in range(1, l + 1):\n\t\tif not i in use:\n\t\t\tarr.append(i)\n\t\tif len(arr) == len(g[ver]):\n\t\t\tbreak\n\tfor to in g[ver]:\n\t\tif paint[to] == -1:\n\t\t\tfor j in range(1, l + 1):\n\t\t\t\tif not j in use:\n\t\t\t\t\tpaint[to] = arr[-1]\n\t\t\t\t\tq.append(to)\n\t\t\t\t\tarr.pop()\n\t\t\t\t\tbreak\nprint(l)\nprint(*paint)\n", "from collections import deque\nn = int(input())\nans = [0] * n\ng = [[] for _ in range(n)]\nfor _ in range(n - 1):\n\t(u, v) = list(map(int, input().split()))\n\tu -= 1\n\tv -= 1\n\tg[u].append(v)\n\tg[v].append(u)\ncol = 1\nq = deque()\nvis = [False] * n\nq.append((0, 0))\nvis[0] = True\nans[0] = 1\np_top = 0\nwhile q:\n\t(top, p_top) = q.popleft()\n\tcol = 1\n\tfor viz in g[top]:\n\t\tif not vis[viz]:\n\t\t\tvis[viz] = True\n\t\t\tq.append((viz, top))\n\t\t\twhile ans[top] == col or ans[p_top] == col:\n\t\t\t\tcol += 1\n\t\t\tans[viz] = col\n\t\t\tcol += 1\nprint(max(ans))\nprint(' '.join(map(str, ans)))\n", "from sys import stdin\nfrom collections import deque\n\ndef main():\n\tn = int(input()) + 1\n\tg = [[] for _ in range(n)]\n\tfor s in range(n - 2):\n\t\t(u, v) = map(int, input().split())\n\t\tg[u].append(v)\n\t\tg[v].append(u)\n\t(cc, palette, q) = ([0] * n, [True] * n, deque(((1, 0, 1),)))\n\tcc[1] = 1\n\twhile q:\n\t\t(u, a, b) = q.popleft()\n\t\tc = 1\n\t\tfor v in g[u]:\n\t\t\tif not cc[v]:\n\t\t\t\twhile c in [a, b]:\n\t\t\t\t\tc += 1\n\t\t\t\tcc[v] = c\n\t\t\t\tq.append((v, b, c))\n\t\t\t\tc += 1\n\tprint(max(cc))\n\tprint(' '.join(map(str, cc[1:])))\nmain()\n", "n = int(input())\narr = [[] for i in range(n)]\nfor i in range(n - 1):\n\t(a, b) = map(int, input().split())\n\tarr[a - 1].append(b - 1)\n\tarr[b - 1].append(a - 1)\ns = max([len(p) for p in arr]) + 1\nprint(s)\ncolored = [0] * n\n\ndef dfs(v, c, d):\n\tcolored[v] = p = c\n\tfor u in arr[v]:\n\t\tif not colored[u]:\n\t\t\tc = c + 1 if c < s else 1\n\t\t\tif c == d:\n\t\t\t\tc = c + 1 if c < s else 1\n\t\t\tdfs(u, c, p)\nif s > 3:\n\tdfs(0, 1, 0)\nelse:\n\ti = 0\n\tc = 1\n\twhile len(arr[i]) != 1:\n\t\ti += 1\n\tfor j in range(n):\n\t\tcolored[i] = c\n\t\tc = c + 1 if c < s else 1\n\t\tif j < n - 1:\n\t\t\ti = arr[i][0] if not colored[arr[i][0]] else arr[i][1]\nprint(' '.join(map(str, colored)))\n", "from sys import stdin, stdout\n\ndef INI():\n\treturn int(stdin.readline())\n\ndef INL():\n\treturn [int(_) for _ in stdin.readline().split()]\n\ndef INS():\n\treturn stdin.readline()\n\ndef MOD():\n\treturn pow(10, 9) + 7\n\ndef OPS(ans):\n\tstdout.write(str(ans) + '\\n')\n\ndef OPL(ans):\n\t[stdout.write(str(_) + ' ') for _ in ans]\n\tstdout.write('\\n')\nfrom types import GeneratorType\n\ndef bootstrap(f, stack=[]):\n\n\tdef wrappedfunc(*args, **kwargs):\n\t\tif stack:\n\t\t\treturn f(*args, **kwargs)\n\t\telse:\n\t\t\tto = f(*args, **kwargs)\n\t\t\twhile True:\n\t\t\t\tif type(to) is GeneratorType:\n\t\t\t\t\tstack.append(to)\n\t\t\t\t\tto = next(to)\n\t\t\t\telse:\n\t\t\t\t\tstack.pop()\n\t\t\t\t\tif not stack:\n\t\t\t\t\t\tbreak\n\t\t\t\t\tto = stack[-1].send(to)\n\t\t\treturn to\n\treturn wrappedfunc\n\n@bootstrap\ndef dfs(v, s):\n\tV[v] = True\n\tc = 1\n\tfor _ in X[v]:\n\t\tif not V[_]:\n\t\t\twhile c in s:\n\t\t\t\tc += 1\n\t\t\tC[_] = c\n\t\t\tc += 1\n\tfor _ in X[v]:\n\t\tif not V[_]:\n\t\t\tyield dfs(_, set({C[v], C[_]}))\n\tyield\nn = INI()\nX = [[] for _ in range(n + 1)]\nV = [False for _ in range(n + 1)]\nC = [0 for _ in range(n + 1)]\nfor _ in range(n - 1):\n\t(u, v) = INL()\n\tX[u].append(v)\n\tX[v].append(u)\nC[1] = 1\ndfs(1, set({1}))\nOPS(len(set(C)) - 1)\nOPL(C[1:])\n", "import sys\nsys.setrecursionlimit(200000)\nn = int(input())\ng = [[] for i in range(n)]\nfor i in range(n - 1):\n\t(a, b) = map(int, input().split())\n\tg[a - 1].append(b - 1)\n\tg[b - 1].append(a - 1)\ns = max([len(p) for p in g]) + 1\nprint(s)\nr = [0] * n\n\ndef dfs(v, c, d):\n\tr[v] = p = c\n\tfor u in g[v]:\n\t\tif not r[u]:\n\t\t\tc = c + 1 if c < s else 1\n\t\t\tif c == d:\n\t\t\t\tc = c + 1 if c < s else 1\n\t\t\tdfs(u, c, p)\nif s > 3:\n\tdfs(0, 1, 0)\nelse:\n\ti = 0\n\tc = 1\n\twhile len(g[i]) != 1:\n\t\ti += 1\n\tfor j in range(n):\n\t\tr[i] = c\n\t\tc = c + 1 if c < s else 1\n\t\tif j < n - 1:\n\t\t\ti = g[i][0] if not r[g[i][0]] else g[i][1]\nprint(' '.join(map(str, r)))\n", "import sys\ninput = sys.stdin.readline\nfrom collections import deque\n\ndef bfs():\n\tvisited = [False] * n\n\tvisited[0] = True\n\tcolor = [-1] * n\n\tcolor[0] = 1\n\tq = deque([(0, 1, -1)])\n\twhile q:\n\t\t(v, pre_c1, pre_c2) = q.popleft()\n\t\tcnt = 1\n\t\tfor nv in G[v]:\n\t\t\tif visited[nv]:\n\t\t\t\tcontinue\n\t\t\twhile cnt == pre_c1 or cnt == pre_c2:\n\t\t\t\tcnt += 1\n\t\t\tcolor[nv] = cnt\n\t\t\tcnt += 1\n\t\t\tq.append((nv, color[v], color[nv]))\n\t\t\tvisited[nv] = True\n\treturn color\nn = int(input())\nG = [[] for _ in range(n)]\nfor _ in range(n - 1):\n\t(x, y) = map(int, input().split())\n\tG[x - 1].append(y - 1)\n\tG[y - 1].append(x - 1)\ncolor = bfs()\nprint(max(color))\nprint(*color)\n", "from sys import stdin\ninput = stdin.readline\n\ndef put():\n\treturn map(int, input().split())\n\ndef dfs():\n\ts = [(0, 0)]\n\ttree[0].append(1)\n\twhile s:\n\t\t(i, p) = s.pop()\n\t\tc = 1\n\t\tfor j in tree[i]:\n\t\t\tif j != p:\n\t\t\t\ts.append((j, i))\n\t\t\t\twhile c in [color[i], color[p]]:\n\t\t\t\t\tc += 1\n\t\t\t\tcolor[j] = c\n\t\t\t\tc += 1\nn = int(input())\ntree = [[] for i in range(n + 1)]\ncolor = [0] * (n + 1)\nfor _ in range(n - 1):\n\t(x, y) = put()\n\ttree[x].append(y)\n\ttree[y].append(x)\nans = 0\nfor i in range(1, n + 1):\n\tans = max(ans, len(tree[i]) + 1)\ndfs()\nprint(ans)\nprint(*color[1:])\n", "from collections import defaultdict, deque\n\nclass Graph:\n\n\tdef __init__(self, n):\n\t\tself.graph = defaultdict(list)\n\t\tself.parentColor = [-1] * (n + 1)\n\t\tself.color = [-1] * (n + 1)\n\t\tself.visited = [False] * (n + 1)\n\t\tself.n = n\n\n\tdef addEdge(self, fr, to):\n\t\tself.graph[fr].append(to)\n\t\tself.graph[to].append(fr)\n\n\tdef BFS(self, root):\n\t\tqueue = deque()\n\t\tqueue.append(root)\n\t\tself.color[root] = 1\n\t\tself.parentColor[root] = 0\n\t\twhile queue:\n\t\t\ts = queue.popleft()\n\t\t\tSet = defaultdict(bool)\n\t\t\tSet[self.color[s]] = True\n\t\t\tSet[self.parentColor[s]] = True\n\t\t\tculur = 1\n\t\t\tfor i in self.graph[s]:\n\t\t\t\tif self.visited[i] == False:\n\t\t\t\t\tqueue.append(i)\n\t\t\t\t\tself.parentColor[i] = self.color[s]\n\t\t\t\t\twhile 1:\n\t\t\t\t\t\tif not Set[culur]:\n\t\t\t\t\t\t\tself.color[i] = culur\n\t\t\t\t\t\t\tculur += 1\n\t\t\t\t\t\t\tbreak\n\t\t\t\t\t\tculur += 1\n\t\t\tself.visited[s] = True\n\n\tdef show(self):\n\t\tprint(max(self.color))\n\t\tprint(*self.color[1:])\nn = int(input())\nG = Graph(n)\nfor _ in range(n - 1):\n\t(a, b) = map(int, input().split())\n\tG.addEdge(a, b)\nG.BFS(1)\nG.show()\n", "from collections import deque\n\ndef ri():\n\treturn list(map(int, input().split()))\nn = int(input())\nv = [0] * n\nc = [0] * n\np = [0] * n\nadj = [set() for i in range(n)]\nfor i in range(n - 1):\n\t(a, b) = ri()\n\ta -= 1\n\tb -= 1\n\tadj[a].add(b)\n\tadj[b].add(a)\nfor s in range(n):\n\tif len(adj[s]) == 1:\n\t\tbreak\nans = 0\nq = deque()\nq.append(s)\nv[s] = 1\nc[s] = 1\np[s] = s\nwhile q:\n\tn = q.popleft()\n\tcc = 1\n\tfor a in adj[n]:\n\t\tif v[a] == 0:\n\t\t\twhile cc in [c[n], c[p[n]]]:\n\t\t\t\tcc += 1\n\t\t\tc[a] = cc\n\t\t\tcc += 1\n\t\t\tans = max(2 + len(adj[a]) - 1, ans)\n\t\t\tq.append(a)\n\t\t\tp[a] = n\n\t\t\tv[a] = 1\nprint(ans)\nprint(' '.join(map(str, c)))\n", "import sys\n\ndef input():\n\treturn sys.stdin.buffer.readline().strip()\nn = int(input())\nadj = [[] for _ in range(n + 1)]\nfor _ in range(n - 1):\n\t(a, b) = map(int, input().split())\n\tadj[a].append(b)\n\tadj[b].append(a)\ncl = [0] * (n + 1)\npar = [0] * (n + 1)\n\ndef dfs(adj, i):\n\tvis = [0] * (n + 1)\n\tq = [i]\n\tcl[1] = 1\n\twhile len(q) > 0:\n\t\tu = q[-1]\n\t\tif vis[u] == 0:\n\t\t\tvis[u] = 1\n\t\t\tc = 1\n\t\t\tfor v in adj[u]:\n\t\t\t\tif vis[v] == 0:\n\t\t\t\t\twhile c == cl[u] or c == cl[par[u]]:\n\t\t\t\t\t\tc += 1\n\t\t\t\t\tcl[v] = c\n\t\t\t\t\tpar[v] = u\n\t\t\t\t\tc += 1\n\t\t\t\t\tq.append(v)\n\t\telse:\n\t\t\tq.pop()\nm = 0\nfor i in range(1, n + 1):\n\tm = max(m, len(adj[i]) + 1)\nprint(m)\ndfs(adj, 1)\nfor i in range(1, n + 1):\n\tprint(cl[i], end=' ')\n", "import sys\nsys.setrecursionlimit(100000)\nfrom collections import deque\nUNDEF = 0\nn = int(input())\ng = [[] for _ in range(n + 1)]\nfor _ in range(n - 1):\n\t(u, v) = map(int, input().split())\n\tg[u].append(v)\n\tg[v].append(u)\nc = [UNDEF] * (n + 1)\nc[1] = 1\n\ndef dfs(par, v):\n\tcur = 1\n\tfor to in g[v]:\n\t\tif c[to] != UNDEF:\n\t\t\tcontinue\n\t\twhile cur in (c[par], c[v]):\n\t\t\tcur += 1\n\t\tc[to] = cur\n\t\tcur += 1\n\t\tdfs(v, to)\n\ndef bfs():\n\tq = deque([(0, 1)])\n\twhile q:\n\t\tcur = 1\n\t\t(par, v) = q.pop()\n\t\tfor to in g[v]:\n\t\t\tif c[to] != UNDEF:\n\t\t\t\tcontinue\n\t\t\twhile cur in (c[par], c[v]):\n\t\t\t\tcur += 1\n\t\t\tc[to] = cur\n\t\t\tcur += 1\n\t\t\tq.appendleft((v, to))\nbfs()\nprint('%d\\n%s' % (max(c), ' '.join(map(str, c[1:]))))\n", "from sys import stdin\ninput = lambda : stdin.readline().strip()\nfrom math import ceil, sqrt, factorial, gcd\nfrom collections import deque\nn = int(input())\ngraph = {i: set() for i in range(n)}\nfor i in range(n - 1):\n\t(a, b) = list(map(int, input().split()))\n\tgraph[a - 1].add(b - 1)\n\tgraph[b - 1].add(a - 1)\nma = 0\nfor i in graph:\n\tif len(graph[i]) + 1 > ma:\n\t\tma = len(graph[i]) + 1\n\t\tx = i\nprint(ma)\nans = [0 for i in range(n)]\nstack = [x]\npapa = [0 for i in range(n)]\nwhile stack:\n\tx = stack.pop()\n\ta = 1\n\tif ans[x] == 0:\n\t\tans[x] = 1\n\t\tz = [1]\n\telse:\n\t\tz = []\n\t\tz.append(ans[x])\n\t\tz.append(ans[papa[x]])\n\tfor j in graph[x]:\n\t\twhile 1:\n\t\t\tif a in z:\n\t\t\t\ta += 1\n\t\t\telse:\n\t\t\t\tans[j] = a\n\t\t\t\ta += 1\n\t\t\t\tbreak\n\t\tstack.append(j)\n\t\tgraph[j].remove(x)\n\t\tpapa[j] = x\nprint(*ans)\n", "import sys\nfrom collections import defaultdict\nfrom collections import deque\nfrom types import GeneratorType\ninput = sys.stdin.readline\n\ndef bootstrap(f, stack=[]):\n\n\tdef wrappedfunc(*args, **kwargs):\n\t\tif stack:\n\t\t\treturn f(*args, **kwargs)\n\t\telse:\n\t\t\tto = f(*args, **kwargs)\n\t\t\twhile True:\n\t\t\t\tif type(to) is GeneratorType:\n\t\t\t\t\tstack.append(to)\n\t\t\t\t\tto = next(to)\n\t\t\t\telse:\n\t\t\t\t\tstack.pop()\n\t\t\t\t\tif not stack:\n\t\t\t\t\t\tbreak\n\t\t\t\t\tto = stack[-1].send(to)\n\t\t\treturn to\n\treturn wrappedfunc\n\ndef get_adj_mat(src, dst):\n\tmatrix = defaultdict(list)\n\tfor (src_i, dst_i) in zip(src, dst):\n\t\tmatrix[src_i].append(dst_i)\n\t\tmatrix[dst_i].append(src_i)\n\treturn matrix\n\n@bootstrap\ndef set_colour(curr_index, parent_index, adj_mat, colours):\n\tval = 1\n\t(curr_val, parent_val) = (colours[curr_index], colours[parent_index])\n\tfor child_index in adj_mat[curr_index]:\n\t\tif child_index != parent_index:\n\t\t\twhile val in [curr_val, parent_val]:\n\t\t\t\tval += 1\n\t\t\tcolours[child_index] = val\n\t\t\tval += 1\n\t\t\tyield set_colour(child_index, curr_index, adj_mat, colours)\n\tyield None\n\ndef solve(src, dst, n):\n\tadj_mat = get_adj_mat(src, dst)\n\tcolours = [-1] * n\n\troot = 0\n\tcolours[root] = 1\n\tset_colour(0, 0, adj_mat, colours)\n\tprint(max(colours))\n\tprint(*colours)\nn = int(input())\n(src, dst) = ([], [])\nfor _ in range(n - 1):\n\t(src_i, dst_i) = [int(val) for val in input().split()]\n\t(src.append(src_i - 1), dst.append(dst_i - 1))\nsolve(src, dst, n)\n", "from sys import stdin\n\ndef main():\n\tn = int(input()) + 1\n\tg = [[] for _ in range(n)]\n\tfor s in stdin.read().splitlines():\n\t\t(u, v) = map(int, s.split())\n\t\tg[u].append(v)\n\t\tg[v].append(u)\n\t(cc, palette, nxt) = ([0] * n, [True] * n, [(1, 0, 1)])\n\tcc[1] = 1\n\twhile nxt:\n\t\t(cur, nxt) = (nxt, [])\n\t\tfor (u, a, b) in cur:\n\t\t\tpalette[a] = palette[b] = False\n\t\t\tc = 1\n\t\t\tfor v in g[u]:\n\t\t\t\tif not cc[v]:\n\t\t\t\t\twhile not palette[c]:\n\t\t\t\t\t\tc += 1\n\t\t\t\t\tcc[v] = c\n\t\t\t\t\tnxt.append((v, b, c))\n\t\t\t\t\tc += 1\n\t\t\tpalette[a] = palette[b] = True\n\tprint(max(cc))\n\tprint(' '.join(map(str, cc[1:])))\nmain()\n", "import sys\ninput = sys.stdin.readline\n\ndef dfs():\n\tstack = [(0, 0)]\n\td[0].append(1)\n\twhile stack:\n\t\t(i, p) = stack.pop()\n\t\tc = 1\n\t\tfor j in d[i]:\n\t\t\tif j != p:\n\t\t\t\tstack.append((j, i))\n\t\t\t\twhile c in {color[i], color[p]}:\n\t\t\t\t\tc = c + 1\n\t\t\t\tcolor[j] = c\n\t\t\t\tc = c + 1\nn = int(input())\nd = {}\nd[0] = []\nfor _ in range(n - 1):\n\t(x, y) = map(int, input().split())\n\tif x in d:\n\t\td[x].append(y)\n\telse:\n\t\td[x] = [y]\n\tif y in d:\n\t\td[y].append(x)\n\telse:\n\t\td[y] = [x]\nm = 0\nfor i in d:\n\tif len(d[i]) > m:\n\t\tm = len(d[i])\nans = m + 1\ncolor = [-1] * (n + 1)\ndfs()\nprint(ans)\nprint(*color[1:])\n", "from collections import deque\nn = int(input())\ndic = {}\nfor i in range(n):\n\tdic[i] = []\nfor i in range(n - 1):\n\t(a, b) = map(int, input().split())\n\tdic[a - 1].append(b - 1)\n\tdic[b - 1].append(a - 1)\ncolor = {}\nprevcolor = {}\ncolor[0] = 1\nprevcolor[0] = 1\nlis = deque()\nlis.append(0)\nvisited = {}\nwhile len(lis) != 0:\n\tt = lis.popleft()\n\tcol = 0\n\tvisited[t] = 1\n\tprev = prevcolor[t]\n\tfor i in dic[t]:\n\t\ttry:\n\t\t\tz = visited[i]\n\t\texcept:\n\t\t\twhile col == prev or col == color[t] or col == prevcolor[t]:\n\t\t\t\tcol += 1\n\t\t\tcolor[i] = col\n\t\t\tprevcolor[i] = color[t]\n\t\t\tlis.append(i)\n\t\t\tprev = col\nprint(max(color.values()) + 1)\nfor i in range(n):\n\tprint(color[i] + 1, end=' ')\n"]

difficulty: MEDIUM

source: codeforces

raw_problem:
C. Andryusha and Colored Balloons

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Andryusha goes through a park each day. The squares and paths between them look boring to Andryusha, so he decided to decorate them.

The park consists of n squares connected with (n - 1) bidirectional paths in such a way that any square is reachable from any other using these paths. Andryusha decided to hang a colored balloon at each of the squares. The baloons' colors are described by positive integers, starting from 1. In order to make the park varicolored, Andryusha wants to choose the colors in a special way. More precisely, he wants to use such colors that if a, b and c are distinct squares that a and b have a direct path between them, and b and c have a direct path between them, then balloon colors on these three squares are distinct.

Andryusha wants to use as little different colors as possible. Help him to choose the colors!

Input

The first line contains single integer n (3 ≤ n ≤ 2·105) — the number of squares in the park.

Each of the next (n - 1) lines contains two integers x and y (1 ≤ x, y ≤ n) — the indices of two squares directly connected by a path.

It is guaranteed that any square is reachable from any other using the paths.

Output

In the first line print single integer k — the minimum number of colors Andryusha has to use.

In the second line print n integers, the i-th of them should be equal to the balloon color on the i-th square. Each of these numbers should be within range from 1 to k.

Examples

Input

3
2 3
1 3

Output

3
1 3 2

Input

5
2 3
5 3
4 3
1 3

Output

5
1 3 2 5 4

Input

5
2 1
3 2
4 3
5 4

Output

3
1 2 3 1 2

Note

In the first sample the park consists of three squares: 1 → 3 → 2. Thus, the balloon colors have to be distinct.
  Illustration for the first sample.
In the second example there are following triples of consequently connected squares:

 1 → 3 → 2

 1 → 3 → 4

 1 → 3 → 5

 2 → 3 → 4

 2 → 3 → 5

 4 → 3 → 5

 We can see that each pair of squares is encountered in some triple, so all colors have to be distinct.  Illustration for the second sample.
In the third example there are following triples:

 1 → 2 → 3

 2 → 3 → 4

 3 → 4 → 5

 We can see that one or two colors is not enough, but there is an answer that uses three colors only.  Illustration for the third sample.

question:
Andryusha goes through a park each day. The squares and paths between them look boring to Andryusha, so he decided to decorate them.
The park consists of n squares connected with (n - 1) bidirectional paths in such a way that any square is reachable from any other using these paths. Andryusha decided to hang a colored balloon at each of the squares. The baloons' colors are described by positive integers, starting from 1. In order to make the park varicolored, Andryusha wants to choose the colors in a special way. More precisely, he wants to use such colors that if a, b and c are distinct squares that a and b have a direct path between them, and b and c have a direct path between them, then balloon colors on these three squares are distinct.
Andryusha wants to use as little different colors as possible. Help him to choose the colors!

Input
The first line contains single integer n (3 ≤ n ≤ 2·10^{5}) — the number of squares in the park.
Each of the next (n - 1) lines contains two integers x and y (1 ≤ x, y ≤ n) — the indices of two squares directly connected by a path.
It is guaranteed that any square is reachable from any other using the paths.

Output
In the first line print single integer k — the minimum number of colors Andryusha has to use.
In the second line print n integers, the i-th of them should be equal to the balloon color on the i-th square. Each of these numbers should be within range from 1 to k.

Examples
Input
3
2 3
1 3

Output
3
1 3 2

Input
5
2 3
5 3
4 3
1 3

Output
5
1 3 2 5 4

Input
5
2 1
3 2
4 3
5 4

Output
3
1 2 3 1 2

Note
In the first sample the park consists of three squares: 1 → 3 → 2. Thus, the balloon colors have to be distinct.
 ![image](1.png) Illustration for the first sample. In the second example there are following triples of consequently connected squares:
 -  1 → 3 → 2 -  1 → 3 → 4 -  1 → 3 → 5 -  2 → 3 → 4 -  2 → 3 → 5 -  4 → 3 → 5  We can see that each pair of squares is encountered in some triple, so all colors have to be distinct. ![image](2.png) Illustration for the second sample. In the third example there are following triples:
 -  1 → 2 → 3 -  2 → 3 → 4 -  3 → 4 → 5  We can see that one or two colors is not enough, but there is an answer that uses three colors only. ![image](3.png) Illustration for the third sample.

image_tags: Graph Graph Tree

data_split: test


E. Sonya and Ice Cream

problem_index: E

time_limit: 2 seconds

memory_limit: 256 megabytes

note:
In the first example, you can choose the path 2-4, so the answer will be 4.
![image](images/cf_1004_E/1.png) The first example.
In the second example, you can choose the path 4-1-2, so the answer will be 7.
![image](images/cf_1004_E/2.png) The second example.

source: codeforces

raw_problem:
E. Sonya and Ice Cream

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Sonya likes ice cream very much. She eats it even during programming competitions. That is why the girl decided that she wants to open her own ice cream shops.

Sonya lives in a city with $$$n$$$ junctions and $$$n-1$$$ streets between them. All streets are two-way and connect two junctions. It is possible to travel from any junction to any other using one or more streets. City Hall allows opening shops only on junctions. The girl cannot open shops in the middle of streets.

Sonya has exactly $$$k$$$ friends whom she can trust. If she opens a shop, one of her friends has to work there and not to allow anybody to eat an ice cream not paying for it. Since Sonya does not want to skip an important competition, she will not work in shops personally.

Sonya wants all her ice cream shops to form a simple path of the length $$$r$$$ ($$$1 \le r \le k$$$), i.e. to be located in different junctions $$$f_1, f_2, \dots, f_r$$$ and there is street between $$$f_i$$$ and $$$f_{i+1}$$$ for each $$$i$$$ from $$$1$$$ to $$$r-1$$$.

The girl takes care of potential buyers, so she also wants to minimize the maximum distance between the junctions to the nearest ice cream shop. The distance between two junctions $$$a$$$ and $$$b$$$ is equal to the sum of all the street lengths that you need to pass to get from the junction $$$a$$$ to the junction $$$b$$$. So Sonya wants to minimize

$$$$$$\max_{a} \min_{1 \le i \le r} d_{a,f_i}$$$$$$

where $$$a$$$ takes a value of all possible $$$n$$$ junctions, $$$f_i$$$ — the junction where the $$$i$$$-th Sonya's shop is located, and $$$d_{x,y}$$$ — the distance between the junctions $$$x$$$ and $$$y$$$.

Sonya is not sure that she can find the optimal shops locations, that is why she is asking you to help her to open not more than $$$k$$$ shops that will form a simple path and the maximum distance between any junction and the nearest shop would be minimal.

Input

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1\leq k\leq n\leq 10^5$$$) — the number of junctions and friends respectively.

Each of the next $$$n-1$$$ lines contains three integers $$$u_i$$$, $$$v_i$$$, and $$$d_i$$$ ($$$1\leq u_i, v_i\leq n$$$, $$$v_i\neq u_i$$$, $$$1\leq d\leq 10^4$$$) — junctions that are connected by a street and the length of this street. It is guaranteed that each pair of junctions is connected by at most one street. It is guaranteed that you can get from any junctions to any other.

Output

Print one number — the minimal possible maximum distance that you need to pass to get from any junction to the nearest ice cream shop. Sonya's shops must form a simple path and the number of shops must be at most $$$k$$$.

Examples

Input

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

Output

4

Input

10 3
1 2 5
5 7 2
3 2 6
10 6 3
3 8 1
6 4 2
4 1 6
6 9 4
5 2 5

Output

7

Note

In the first example, you can choose the path 2-4, so the answer will be 4.
  The first example.
In the second example, you can choose the path 4-1-2, so the answer will be 7.
  The second example.

question:
Sonya likes ice cream very much. She eats it even during programming competitions. That is why the girl decided that she wants to open her own ice cream shops.
Sonya lives in a city with $$$n$$$ junctions and $$$n-1$$$ streets between them. All streets are two-way and connect two junctions. It is possible to travel from any junction to any other using one or more streets. City Hall allows opening shops only on junctions. The girl cannot open shops in the middle of streets.
Sonya has exactly $$$k$$$ friends whom she can trust. If she opens a shop, one of her friends has to work there and not to allow anybody to eat an ice cream not paying for it. Since Sonya does not want to skip an important competition, she will not work in shops personally.
Sonya wants all her ice cream shops to form a simple path of the length $$$r$$$ ($$$1 \le r \le k$$$), i.e. to be located in different junctions $$$f_1, f_2, \dots, f_r$$$ and there is street between $$$f_i$$$ and $$$f_{i+1}$$$ for each $$$i$$$ from $$$1$$$ to $$$r-1$$$.
The girl takes care of potential buyers, so she also wants to minimize the maximum distance between the junctions to the nearest ice cream shop. The distance between two junctions $$$a$$$ and $$$b$$$ is equal to the sum of all the street lengths that you need to pass to get from the junction $$$a$$$ to the junction $$$b$$$. So Sonya wants to minimize
$$$$$$\max_{a} \min_{1 \le i \le r} d_{a,f_i}$$$$$$
where $$$a$$$ takes a value of all possible $$$n$$$ junctions, $$$f_i$$$ — the junction where the $$$i$$$-th Sonya's shop is located, and $$$d_{x,y}$$$ — the distance between the junctions $$$x$$$ and $$$y$$$.
Sonya is not sure that she can find the optimal shops locations, that is why she is asking you to help her to open not more than $$$k$$$ shops that will form a simple path and the maximum distance between any junction and the nearest shop would be minimal.

Input
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1\leq k\leq n\leq 10^5$$$) — the number of junctions and friends respectively.
Each of the next $$$n-1$$$ lines contains three integers $$$u_i$$$, $$$v_i$$$, and $$$d_i$$$ ($$$1\leq u_i, v_i\leq n$$$, $$$v_i\neq u_i$$$, $$$1\leq d\leq 10^4$$$) — junctions that are connected by a street and the length of this street. It is guaranteed that each pair of junctions is connected by at most one street. It is guaranteed that you can get from any junctions to any other.

Output
Print one number — the minimal possible maximum distance that you need to pass to get from any junction to the nearest ice cream shop. Sonya's shops must form a simple path and the number of shops must be at most $$$k$$$.

Examples
Input
6 2
1 2 3
2 3 4
4 5 2
4 6 3
2 4 6

Output
4

Input
10 3
1 2 5
5 7 2
3 2 6
10 6 3
3 8 1
6 4 2
4 1 6
6 9 4
5 2 5

Output
7

Note
In the first example, you can choose the path 2-4, so the answer will be 4.
 ![image](1.png) The first example. In the second example, you can choose the path 4-1-2, so the answer will be 7.
 ![image](2.png) The second example.

tags: ['Shortest paths', 'Sorting', 'Greedy algorithms', 'Tree algorithms', 'Dynamic programming', 'Data structures']

skill_types: ['Dynamic programming', 'Sorting', 'Data structures', 'Greedy algorithms']

raw_tags: ['data structures', 'greedy', 'shortest paths', 'binary search', 'dp', 'trees']

image_tags: Graph Graph

data_split: test