L - Schedule Adjustment Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

高橋君は文化祭のステージ発表のスケジュールを管理しています。ここでは各発表の開始時刻のみを考え、発表の所要時間は考慮しません。

発表者は N 人います。発表者 i (1 \leq i \leq N) の発表開始時刻には 2 つの候補があります。時刻 A_i 分に開始するか、ちょうど D_i 分だけ遅らせて時刻 A_i + D_i 分に開始するかのいずれかです。

高橋君は、各発表者について遅らせるかどうかを決定します。その決定を 0 と 1 のみからなる長さ N の文字列 S で表します。

  • S_i = 0 のとき、発表者 i は時刻 A_i 分に発表を開始します。
  • S_i = 1 のとき、発表者 i は時刻 A_i + D_i 分に発表を開始します。

また、観客が共通しているために発表開始時刻をなるべく離したい M 組の発表者の対が与えられます。j 番目の対 (1 \leq j \leq M) は発表者 U_j と発表者 V_j からなります。

文字列 S に対し、f(S) を次のように定めます。

  • 各対 j (1 \leq j \leq M) について「発表者 U_j の実際の発表開始時刻と発表者 V_j の実際の発表開始時刻の差の絶対値」を求め、それらの最小値を f(S) とする。

f(S) を最大化することが高橋君の目標です。f(S) の最大値を K とするとき、以下を求めてください。

  1. K の値
  2. f(S) = K を達成する文字列 S のうち、辞書順最小のもの

ここで、文字列の辞書順比較は 0 < 1 として行います。

制約

  • 1 \leq N \leq 2000
  • 1 \leq M \leq 5000
  • N \times M \leq 10^6
  • 0 \leq A_i \leq 10^9
  • 1 \leq D_i \leq 10^9
  • 1 \leq U_j, V_j \leq N
  • U_j \neq V_j
  • (U_j, V_j) の組は順序を無視してすべて異なる
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1 D_1
A_2 D_2
\vdots
A_N D_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M

N は発表者の人数、M は対の数である。A_i は発表者 i の予定開始時刻（分）、D_i は発表者 i の遅延可能時間（分）である。U_j, V_j は j 番目の対を構成する発表者の番号である。

出力

以下の形式で出力してください。

K
S

1 行目に f(S) の最大値 K を、2 行目に f(S) = K を達成する辞書順最小の文字列 S を出力してください。

入力例 1

3 2
10 5
12 10
30 3
1 2
2 3

出力例 1

11
011

入力例 2

4 4
0 10
10 5
18 2
25 10
1 2
2 3
3 4
1 4

出力例 2

10
0011

入力例 3

8 10
5 7
20 4
13 15
40 10
0 30
55 5
25 20
70 8
1 2
1 3
2 4
3 4
3 5
4 6
5 7
6 8
2 7
1 8

出力例 3

12
00100010

入力例 4

15 25
100 30
150 20
80 100
300 40
260 75
400 10
50 200
500 60
620 80
700 25
710 90
900 100
850 30
1000 150
1100 50
1 2
1 3
1 7
2 3
2 4
2 8
3 5
3 7
4 5
4 6
4 9
5 6
5 10
6 8
6 11
7 8
7 12
8 9
8 13
9 10
9 14
10 11
11 15
12 13
14 15

出力例 4

40
110000100010000

入力例 5

2 1
0 1000000000
1000000000 1000000000
1 2

出力例 5

2000000000
01

Score : 500 pts

Problem Statement

Takahashi is managing the schedule of stage presentations for a school festival. Here, we only consider the start time of each presentation, and the duration of the presentations is not considered.

There are N presenters. Presenter i (1 \leq i \leq N) has two candidate start times for their presentation: either starting at time A_i minutes, or delaying it by exactly D_i minutes to start at time A_i + D_i minutes.

Takahashi decides whether to delay the presentation for each presenter. This decision is represented by a string S of length N consisting only of 0 and 1.

  • When S_i = 0, presenter i starts their presentation at time A_i minutes.
  • When S_i = 1, presenter i starts their presentation at time A_i + D_i minutes.

Additionally, we are given M pairs of presenters whose presentation start times should be as far apart as possible because they share some audience members. The j-th pair (1 \leq j \leq M) consists of presenter U_j and presenter V_j.

For a string S, we define f(S) as follows:

  • For each pair j (1 \leq j \leq M), calculate the absolute difference between the actual start time of presenter U_j and the actual start time of presenter V_j. The minimum of these absolute differences is f(S).

Takahashi's goal is to maximize f(S). Let K be the maximum value of f(S). Find the following:

  1. The value of K
  2. The lexicographically smallest string S that achieves f(S) = K.

Here, the lexicographical comparison of strings is performed with 0 < 1.

Constraints

  • 1 \leq N \leq 2000
  • 1 \leq M \leq 5000
  • N \times M \leq 10^6
  • 0 \leq A_i \leq 10^9
  • 1 \leq D_i \leq 10^9
  • 1 \leq U_j, V_j \leq N
  • U_j \neq V_j
  • All pairs (U_j, V_j) are unique, regardless of order.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
A_1 D_1
A_2 D_2
\vdots
A_N D_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M

N is the number of presenters, and M is the number of pairs. A_i is the scheduled start time (in minutes) of presenter i, and D_i is the delay duration (in minutes) for presenter i. U_j and V_j are the indices of the presenters forming the j-th pair.

Output

Output in the following format:

K
S

In the first line, output the maximum value K of f(S). In the second line, output the lexicographically smallest string S that achieves f(S) = K.

Sample Input 1

3 2
10 5
12 10
30 3
1 2
2 3

Sample Output 1

11
011

Sample Input 2

4 4
0 10
10 5
18 2
25 10
1 2
2 3
3 4
1 4

Sample Output 2

10
0011

Sample Input 3

8 10
5 7
20 4
13 15
40 10
0 30
55 5
25 20
70 8
1 2
1 3
2 4
3 4
3 5
4 6
5 7
6 8
2 7
1 8

Sample Output 3

12
00100010

Sample Input 4

15 25
100 30
150 20
80 100
300 40
260 75
400 10
50 200
500 60
620 80
700 25
710 90
900 100
850 30
1000 150
1100 50
1 2
1 3
1 7
2 3
2 4
2 8
3 5
3 7
4 5
4 6
4 9
5 6
5 10
6 8
6 11
7 8
7 12
8 9
8 13
9 10
9 14
10 11
11 15
12 13
14 15

Sample Output 4

40
110000100010000

Sample Input 5

2 1
0 1000000000
1000000000 1000000000
1 2

Sample Output 5

2000000000
01