> For the complete documentation index, see [llms.txt](https://tobigs.gitbook.io/usaco-week2/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://tobigs.gitbook.io/usaco-week2/f.-the-great-revegetation-bronze.md).

# F. The Great Revegetation (Bronze)

크기가 N인 배열 A에 다음 조건을 만족해야합니다.

* M개의 (i, j)쌍에 대해서, A\[ i ] != A\[ j ]

이때 출력되는 답은 배열 A를 정수로 표현했을 때 가장 작아야합니다.

저는 모든 i, j쌍에 대해서(i < j)  A\[ i ] != A\[ j ]이면 A\[ j ]++을 했는데 이러면 틀립니다.

<틀린 풀이>

```python
N, M = map(int,input().split())
p = [1] * N
f = [] 
for _ in range(M):
	x, y = sorted(map(int,input().split()))
	f.append((x, y))

f.sort()

for x, y in f:
	if p[x-1] == p[y-1]: p[y-1] += 1

print(''.join(map(str,p)))
```

반례는 다음과 같습니다.

<입력>

4 3

1 2

2 4

3 4

<틀린 출력> 1212

<정답출력> 1213

반례를 보면 알겠지만 (2, 4)에서 조건을 체크해서 A\[2] = 2, A\[4] = 1이었는데

&#x20;A\[4]가 (3, 4)에서 증가해서 A\[2] = A\[4] = 2 가 되어버렸죠.

그래서 저 틀린 풀이에서 간단하게 (i, j)쌍만이 아니라 (j, i)쌍도 넣으면 정답풀이가 됩니다.

<정답 풀이>&#x20;

```python
N, M = map(int,input().split())
p = [1] * N
f = []
for _ in range(M):
	x,y = map(int,input().split())
	f.append((x-1,y-1))
	f.append((y-1,x-1))

for x, y in sorted(f):
	if p[x] == p[y]:
		if x < y: p[y] += 1
		else: p[x] += 1

print(''.join(map(str,p)))
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://tobigs.gitbook.io/usaco-week2/f.-the-great-revegetation-bronze.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.