Let $P(x)=x+1$ and $Q(x)=x^2+1.$ Consider all sequences $\langle(x_k,y_k)\rangle_{k\in\mathbb{N}}$ such that $(x_1,y_1)=(1,3)$ and $(x_{k+1},y_{k+1})$ is either $(P(x_k), Q(y_k))$ or $(Q(x_k),P(y_k))$ for each $k.  $ We say that a positive integer $n$ is nice if $x_n=y_n$ holds in at least one of these sequences. Find all nice numbers.
1. **Initial Setup and Definitions:**
   - Define the polynomials \( P(x) = x + 1 \) and \( Q(x) = x^2 + 1 \).
   - Consider sequences \(\langle (x_k, y_k) \rangle_{k \in \mathbb{N}}\) such that \((x_1, y_1) = (1, 3)\).
   - For each \(k\), \((x_{k+1}, y_{k+1})\) is either \((P(x_k), Q(y_k))\) or \((Q(x_k), P(y_k))\).

2. **Definition of Nice Numbers:**
   - A positive integer \(n\) is nice if \(x_n = y_n\) holds in at least one of these sequences.

3. **Checking \(n = 3\):**
   - For \(n = 3\), consider the sequence \((1, 3) \to (2, 4) \to (5, 5)\).
   - Clearly, \(x_3 = y_3 = 5\), so \(n = 3\) is a nice number.

4. **Checking \(n = 1\) and \(n = 2\):**
   - For \(n = 1\), \((x_1, y_1) = (1, 3)\), so \(x_1 \neq y_1\).
   - For \(n = 2\), the possible pairs are \((2, 10)\) or \((2, 4)\), neither of which satisfy \(x_2 = y_2\).

5. **General Case for \(n \geq 4\):**
   - **Case 1:** \(x_n = Q(x_{n-1})\) and \(y_n = P(y_{n-1})\).
     - This implies \(x_{n-1}^2 + 1 = y_{n-1} + 1\), so \(x_{n-1} = a\) and \(y_{n-1} = a^2\) for some \(a\).
     - Since \(x_{n-1} \geq x_1 + (n-2)\), we have \(a \geq n-1 \geq 3\).

6. **Behavior of \(y_{n-1}\):**
   - Suppose \(y_{n-1} = Q(y_{n-2}) = y_{n-2}^2 + 1\).
     - This leads to \((a - y_{n-2})(a + y_{n-2}) = 1\), which is impossible since \(a \geq 3\).
   - Therefore, \(y_{n-1} = P(y_{n-2}) = y_{n-2} + 1\) and \(x_{n-1} = Q(x_{n-2}) = x_{n-2}^2 + 1\).

7. **Recursive Step Analysis:**
   - For \((x_{n-2}, y_{n-2}) = (\sqrt{a-1}, a^2 - 1)\), we have \(\sqrt{a-1} > 1\), so \(a = t^2 + 1\) for some \(t \geq 2\).
   - Rewriting, \((x_{n-2}, y_{n-2}) = (t, (t^2 + 1)^2 - 1)\).

8. **Further Analysis:**
   - \(y_{n-2} = P(y_{n-3})\) implies \((t^2 + 1)^2 - 2 = y_{n-3}^2\), which is impossible.
   - Therefore, \(y_{n-2} = P(y_{n-3}) = y_{n-3} + 1\).

9. **Iteration and Growth:**
   - The sequence grows such that \(y_i = P(y_{i-1})\) for a long time.
   - This implies \(y_i - 1\) is not a perfect square for many steps, leading to a contradiction in reaching \(x_n = y_n\).

10. **Conclusion:**
    - The only possible nice number is \(n = 3\).

The final answer is \( \boxed{ n = 3 } \).