Firebase Dynamic Links do not open the app

When I debug the app on my Android device by hitting the play button in Android Studio, then open an email that contains Firebase Dynamic link (actually created by Firebase Auth, we are using email link auth), tapping that link sends me to the app.

When I install the very same app (same code, manifests, etc.) via Play Store and hit the same link, it opens a backup web page instead of the app. Where is the catch?

This is intent filter I am using:

<intent-filter>
    <action android:name="android.intent.action.MAIN"/>
    <category android:name="android.intent.category.LAUNCHER"/>
</intent-filter>
<intent-filter android:autoVerify="true">
    <action android:name="android.intent.action.VIEW"/>
    <category android:name="android.intent.category.DEFAULT"/>
    <category android:name="android.intent.category.BROWSABLE"/>
    <data android:host="arivadev.page.link" android:scheme="http"/>
    <data android:host="arivadev.page.link" android:scheme="https"/>
</intent-filter>

The package and applicationId of the app is sk.adriva.dev. Here you can verify that the auto-verify should work: https://arivadev.page.link/.well-known/assetlinks.json.

Any ideas? Could this be an app signing issue? Something wrong with that SHA-256 certificate fingerprint added via the Firebase console?