#include <bits/stdc++.h>

using namespace std;

// 递归
// 分析：用树图进行分析，说明分枝多，重复多，计算多，速度慢，容易爆栈.从未知到已知，自我调用
int louti(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    return louti(n - 1) + louti(n - 2);
}

//递推
// 分析：无多余运算，速度快，性能好，从已知至未知，推导
int louti2(int n) {
    int a = 1, b = 2, c = 0, i = 3;
    if (n == 1) return a;
    if (n == 2) return b;

    while (i <= n) {
        c = a + b;
        a = b;
        b = c;
        i++;
    }
    return c;
}

int main() {
    int n;
    cin >> n;
    //递归
    cout << louti(n) << endl;
    //递推
    cout << louti2(n) << endl;
    return 0;
}