Determine all pairs $(f,g)$ of functions from the set of positive integers to itself that satisfy \[f^{g(n)+1}(n) + g^{f(n)}(n) = f(n+1) - g(n+1) + 1\] for every positive integer $n$. Here, $f^k(n)$ means $\underbrace{f(f(\ldots f)}_{k}(n) \ldots ))$.

[i]Proposed by Bojan Bašić, Serbia[/i]
1. **Initial Setup and Assumptions:**
   We are given the functional equation:
   \[
   f^{g(n)+1}(n) + g^{f(n)}(n) = f(n+1) - g(n+1) + 1
   \]
   for all positive integers \( n \). Here, \( f^k(n) \) denotes the \( k \)-fold application of \( f \) to \( n \).

2. **Bounding \( f \) in terms of \( g \):**
   Since \( f \) and \( g \) are functions from the set of positive integers to itself, they are always positive. Therefore, we have:
   \[
   f(n+1) - g(n+1) + 1 \geq 1
   \]
   This implies:
   \[
   f(n+1) \geq g(n+1)
   \]
   Since \( f \) and \( g \) are positive, we can further deduce:
   \[
   f(n+1) - g(n+1) + 1 \geq 2
   \]
   Hence:
   \[
   f(n) \geq g(n) + 1 \quad \text{for all } n \geq 2
   \]

3. **Strengthening the Bound:**
   For \( n \geq 2 \), we have:
   \[
   f(n+1) - g(n+1) + 1 \geq f^{g(n)+1}(n) + g^{f(n)}(n) \geq 2 + 1
   \]
   This implies:
   \[
   f(n) \geq g(n) + 2 \quad \text{for all } n \geq 3
   \]
   By induction, we can generalize this to:
   \[
   f(n) \geq g(n) + n - 1 \quad \text{for all } n
   \]
   In particular, this means:
   \[
   f(n) \geq n + (g(n) - 1) \geq n
   \]

4. **Assuming \( f(n) \geq n + 1 \):**
   Suppose \( f(n) \geq n + 1 \). Then:
   \[
   f^k(n) \geq f^{k-1}(n+1) \geq f(n+1)
   \]
   Substituting this into the original equation, we get:
   \[
   f(n+1) - g(n+1) + 1 = f^{g(n)+1}(n) + g^{f(n)}(n) \geq f(n+1) + g(\text{something})
   \]
   This is impossible since \( g \) is positive.

5. **Conclusion for \( f \):**
   Therefore, we must have:
   \[
   f(n) = n \quad \text{for all } n \in \mathbb{N}
   \]

6. **Determining \( g \):**
   Substituting \( f(n) = n \) into the original equation, we get:
   \[
   g^n(n) + g(n+1) = 2
   \]
   Since \( g \) is positive, this implies:
   \[
   g(n+1) = 1 \quad \text{for all } n
   \]
   We need to find \( g(1) \). Setting \( n = 1 \) in the original equation, we get:
   \[
   g(1) = 1
   \]
   Therefore, we have:
   \[
   g(n) = 1 \quad \text{for all } n \in \mathbb{N}
   \]

The final answer is \( \boxed{(f(n) = n, g(n) = 1)} \).